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

· · 题解

Question

给定 a,b，要求 \varphi(a^b) \bmod 998244353 的值。

Solution

我们首先把 a 分解质因数得到 a = \prod_{i=1}^m p_i^{c_i}，那么我们可以发现，对于每一个数，如果它和 a^b 不互质，那么应当至少含有一个 p_i。

因此，我们可以挨个考虑质因子。对于质因子 p_i，我们有 \dfrac{p_i-1}{p_i} 的数不含质因子 p_i，于是得到答案为：

\text{ans} = a^b \times \prod_{i=1}^m \frac{p_i-1}{p_i}

Code

/**
 *    author: luuia
 *    created: 2025.08.28 19:38:18
**/
#include<bits/stdc++.h>
using ll = long long;
#define For(i,j,k) for(ll i = j;i <= k;i++)
using namespace std;
template<typename T> T qpow(T c,T n,T m){T r = 1;for(;n;n >>= 1,c = c * c % m) if(n & 1) r = r * c % m;return r;}
const ll N = 1e6 + 10,p = 998244353;
void sol(){ll a,b;cin >> a >> b;ll o = qpow(a,b,p),m = sqrt(a);
    For(i,2,m){if(a % i == 0) o = o * qpow(i,p - 2,p) % p * (i - 1) % p;
        while(a % i == 0) a /= i;
    }if(a > 1) o = o * qpow(a,p - 2,p) % p * (a - 1) % p;cout << o << '\n';
}int main(){
    // freopen("input.in","r",stdin);
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    ll T = 1;while(T--) sol();return 0;
}

java 版的代码：

/**
 *    author: luuia
 *    created: 2025.08.28 19:38:18
 **/
import java.util.Scanner;

public class Main {
    static final long MOD = 998244353L;

    static long modPow(long a, long e, long mod){
        a %= mod;
        long r = 1;
        while(e > 0){
            if((e & 1L) == 1L) r = r * a % mod;
            a = a * a % mod;
            e >>= 1;
        }
        return r;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        sc.close();

        long o = modPow(a % MOD, b, MOD);
        long m = (long)Math.sqrt(a);
        for(long i = 2; i <= m; ++i){
            if(a % i == 0){
                o = o * modPow(i % MOD, MOD - 2, MOD) % MOD;
                o = o * ((i - 1) % MOD) % MOD;
                while(a % i == 0) a /= i;
            }
        }
        if(a > 1){
            o = o * modPow(a % MOD, MOD - 2, MOD) % MOD;
            o = o * ((a - 1) % MOD) % MOD;
        }
        o %= MOD;
        if(o < 0) o += MOD;
        System.out.println(o);
    }
}