1933C.md

C. Turtle Fingers: Count the Values of k

Link

Solution

一道通过分析数据范围来求解的题，看起来循环套循环复杂度会很猛，但实际上简单一分析会发现20*20的循环就能满足1e6的数据，于是就来到了我最喜欢的六个字：直接暴力即可！

要注意某些会出现重复k的情况，所以需要搞个set去重，虽然看起来实在有点儿丑，但题解它也是这么用的。

Code

#define LL long long

int main()
{
    int t;
    std::cin >> t;
    std::unordered_set<int> ans;
    while (t--) {
        ans.clear();
        LL a, b, l;
        std::cin >> a >> b >> l;
        LL tmpa = 1;
        for (size_t i = 0; i <= 20; i++) {
            LL tmpb = 1;
            for (size_t j = 0; j <= 20; j++) {
                if (tmpa * tmpb > l) break;
                if (l % (tmpa * tmpb) == 0) ans.insert(l / (tmpa * tmpb));
                tmpb *= b;
            }
            tmpa *= a;
            if (tmpa > l) break;
        }
        std::cout << ans.size() << std::endl;
    }
    return 0;
}