蓝桥杯3522 互质数的个数 | 数论

题目传送门

首先根据a^b得出需要使用欧拉函数φ，根据欧拉函数的性质：
$$\begin{gathered} \phi (a^b)=a^{b-1}\ast \phi (a) \\ \phi (n)=n\ast (1-1/p_1)\ast (1-1/p_2)\ast ...\ast (1-1/p_k)，其中p_i为n的质因数 \end{gathered}$$
于是使用python的快速幂函数即可得到结果。

mod = 998244353
a, b = map(int, input().split())# 欧拉函数模版
def euler(x: int) -> int:phi = xfor i in range(2, int(pow(x, 0.5)) + 1):if x % i != 0:continuewhile x % i == 0:x = x // iphi = phi * (i-1) // iif x > 1:phi = phi * (x-1) // xreturn phians = (euler(a) * (pow(a, b-1, mod))) % mod
print(ans)

END✨