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

本文主要是介绍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))
        
        
            
            

这篇关于AcWing--互质数的个数--＞数论（欧拉函数）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---