欧拉函数

欧拉函数

欧拉函数 \(\phi(n)\) 表示小于等于 \(n\) 的和 \(n\) 互质的数的个数。

求一个数 \(n\) 的欧拉函数，设将 \(n\) 质因数分解后的质因数集合为 \(p_{1...m}\) ，则 \(\phi(n)=n*\prod_{i=1}^{m}\frac{p_i-1}{p_i}\).

inline int getphi(int n){
    int ans=n;
    for(int i=2;i*i<=n;i++){
        if(n%i)continue;
        ans=ans/i*(i-1);
        while(n%i==0)n/=i;
    }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}

欧拉定理

若 \(gcd(a,p)=1\)，则 \(a^{\phi(p)}\equiv 1 (\mod p)\).

扩展欧拉定理

\(x^k\equiv x^{k\mod \phi(p)},gcd(x,p)=1\).

\(x^k\equiv x^k,gcd(x,p)!=1,b<\phi(p)(\mod p )\).

\(x^k\equiv x^{k\mod \phi(p)+\phi(p)},gcd(a,p)!=1,b>\phi(p)(\mod p)\).