蓝桥杯 互质数的个数
题目
链接
思路
知道欧拉函数的性质就会做了
代码
# 欧拉函数
def euler(n):
res = n
# 找所有的质数因子
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
# 去除因子的k次方
while n % i == 0:
n //= i
res = res // i * (i - 1) # 先除再乘，结果肯定变小，肯定不会大过mod
# 没有质数因子，即n本身就是质数（易忘点）
if n > 1:
res = res // n * (n - 1)
return res
# 快速幂
def ksm(a, b):
x = 1
while b:
if b % 2:
x = x * a % mod
a = a * a % mod
b //= 2
return x
mod = 998244353
a, b = map(int, input().split())
print(ksm(a, b - 1) * euler(a) % mod)
评价
偏数学的题目，知道就是会，不知道就是不会