蓝桥杯3522 互质数的个数 | 数论
题目传送门
首先根据a^b得出需要使用欧拉函数φ，根据欧拉函数的性质：
φ
(
a
b
)
=
a
b
−
1
∗
φ
(
a
)
φ
(
n
)
=
n
∗
(
1
−
1
/
p
1
)
∗
(
1
−
1
/
p
2
)
∗
.
.
.
∗
(
1
−
1
/
p
k
)
，其中
p
i
为
n
的质因数
φ(a^b)=a^{b-1}*φ(a)\\ φ(n)=n*(1-1/p_1)*(1-1/p_2)*...*(1-1/p_k)，其中p_i为n的质因数
φ(ab)=ab−1∗φ(a)φ(n)=n∗(1−1/p1)∗(1−1/p2)∗...∗(1−1/pk)，其中pi为n的质因数
于是使用python的快速幂函数即可得到结果。
mod = 998244353
a, b = map(int, input().split())
# 欧拉函数模版
def euler(x: int) -> int:
phi = x
for i in range(2, int(pow(x, 0.5)) + 1):
if x % i != 0:
continue
while x % i == 0:
x = x // i
phi = phi * (i-1) // i
if x > 1:
phi = phi * (x-1) // x
return phi
ans = (euler(a) * (pow(a, b-1, mod))) % mod
print(ans)
END✨