題目概述

原題參考：C. Turtle Fingers: Count the Values of k
給出整數a，b，l，可以證明l=ka^xb^y，問k最多有多少種選擇

思路分析

這個題我是往往沒想到暴力的，因為我覺得會比較大，但是事實上1e18才是2的五十多次，次方的時間復雜度真不高
我在做的時候實在想著容斥原理(苦笑)，因為很容易看出來，當gcd(a, b)=1時，答案就是兩者的一個排列，所以我在想當兩者的gcd不為1時，是否可以通過容斥解決

參考代碼

#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<long long>
#define ll long long
#define ull unsigned long long
const ll INF = 9187201950435737471;
const int inf = 2139062143;
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1.0);
int a, b, l, am, bm;
set<int> ans;
ll qpw(ll a, ll b, ll p) {
    ll res = 1;
    a %= p;
    while(b) {
        if(b&1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
void solve() {
    ans.clear();
    cin >> a >> b >> l;
    if(a > b) swap(a, b);
    for(int x=0; qpw(a, x, mod) <= l; x++) {
        for(int y=0; qpw(b, y, mod) <= l; y++) {
            if(l % qpw(a, x, mod) == 0 && l / qpw(a, x, mod) % qpw(b, y, mod) == 0) ans.insert(l / qpw(a, x, mod) / qpw(b, y, mod));
            else break;
        }
    }
    cout << ans.size() << endl;
}
int main() {
#ifdef xrl
    freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
#endif
    FAST_IO;
    int t = 1;
    cin >> t;
    while(t --) solve();
#ifdef xrl
    cout << "Time used = " << (double)(clock() * 1.0 / CLOCKS_PER_SEC) << "s";
#endif
    return 0;
}

做題反思

冪次方時間復雜度真不高！！！