AcWing--互质数的个数--＞数论（欧拉函数）

AcWing 4968. 互质数的个数 - AcWing(python)

# 输入
a,b=map(int,input().split())
mod=998244353
# 快速幂取模模板：
def qmi(a,b):
? ? res=1
? ? while(b):
? ? ? ? if(b&1):
? ? ? ? ? ? res=res*a %mod
? ? ? ? a=a*a%mod
? ? ? ? b>>=1
? ? return res

# 欧拉函数
# 质因数

# 判断特例
if (a == 1):
? ? print(0)
? ??
else:
? ? res= a
? ? x=a
? ? # 分解质因数模板
? ? i=2
? ? while i*i<=x:
? ? ? ? if x%i==0:
? ? ? ? ? ? while x % i==0:
? ? ? ? ? ? ? ? x //=i
? ? ? ? ? ? res=res//i *(i-1)
? ? ? ??
? ? ? ? i+=1
? ? if x>1:
? ? ? ? res=res /x* (x-1)
? ? print(int(res*qmi(a,b-1)%mod))
? ? ? ??
? ? ? ??
? ? ? ? ? ??
? ? ? ? ? ??