题解：P13880 [蓝桥杯 2023 省 Java A] 互质数的个数

· · 题解

Solution

我的方法有一点点笨拙，但比较好想，也比较好理解吧。

诸君且看：

a=\prod_{i=1}^{n}{p_i}^{k_i}

则

\begin{aligned} \varphi(a^b)&=\varphi(\prod_{i=1}^{n}{p_i}^{k_i b}) \\ &=\prod_{i=1}^{n}{\varphi({p_i}^{k_i b})} \\ &=\prod_{i=1}^{n}{p_i^{k_i b-1}(p_i-1)} \end{aligned}

考虑一下时间复杂度。使用快速幂计算每个 p_i^{k_i b-1} 需要 \log(k_i b-1)，最大 64 左右；n 最大是 \sqrt{a}；那么总的时间复杂度就是 O(64\sqrt{a})，能够通过本题。

代码和思路部分完全一致，也放在这里了。

#include <iostream>
#include <vector>
#define int long long
using namespace std;
const int MOD = 998244353;
int a, b, ans = 1;
vector<pair<int, int> > p;
void Prime(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            p.push_back(make_pair(i, 0));
            while (n % i == 0) n /= i, p.back().second++;
            p.back().second *= b;
        }
    }
    if (n > 1) p.push_back(make_pair(n, b));
}
int Pow(int x, int n) {
    int res = 1;
    while (n) {
        if (n & 1) (res *= x) %= MOD;
        (x *= x) %= MOD;
        n >>= 1;
    }
    return res;
}
signed main() {
    cin >> a >> b;
    Prime(a);
    for (int i = 0; i < p.size(); i++) {
        int t = p[i].first, cnt = p[i].second;
        (ans *= (t - 1) * Pow(t, cnt - 1) % MOD) %= MOD;
    }
    cout << ans << '\n';
    return 0;
}