Euler函数

欧拉函数:(varphi (n)) 小于等于n的数中与n互质的数的个数

(varphi (1)=1)（小于等于1的正整数中唯一和1互质的数就是1本身）。

若n是质数p的k次幂， (varphi (n)=varphi (p^{k})=p^{k}-p^{k-1}=(p-1)p^{k-1})，因为除了p的倍数外，其他数都跟n互质。

若 p 是质数 (varphi(p)=p-1)

欧拉函数是积性函数，即是说若m,n互质，(varphi (mn)=varphi (m)varphi (n))。

若(n=p_1^{k_1}p_2^{k_2}cdots p_r^{k_r})

则 (varphi (n)=nprod _{i=1}^r(1-{frac {1}{p_i}}))。

所以，能通过O((sqrt n) )的时间，求出(varphi (n))

template<class T>
T euler(T n){
    T res=n;
    for(int i=2;i*i<=n;++i){//任何数最多只有一个大于根号n质因子。
        if(n%i==0){
            res-=res/i;
            while(n%i==0)n/=i;//将因子i全部除去，防止合数被筛
        }
    }
    if(n>1)res-=res/n;//若有大于根号n的质因子
    return res;
}

线性筛欧拉函数：

1. (varphi(p)=p-1)
2. (varphi(i imes p)=p imesvarphi (i) ,(imod p = 0))
3. (varphi(i imes p)=varphi(p) imesvarphi (i)=(p-1) imes varphi(i), (imod p eq 0）)

const int MAXN=3e6+8;
int phi[MAXN];
int prime[MAXN],cnt;
bool nprime[MAXN];
void getphi(){
    phi[1]=1;
    for(int i=2;i<MAXN;++i){
        if(!nprime[i]){
            prime[++cnt]=i;
            phi[i]=i-1;//素数的phi值等于p-1
        }
        for(int j=1;j<=cnt&&prime[j]*i<MAXN;++j){
            nprime[prime[j]*i]=1;
            if(i%prime[j]==0){
                phi[prime[j]*i]=prime[j]*phi[i];// i是p的倍数
                break;
            }
            else phi[prime[j]*i]=phi[i]*(prime[j]-1);//i，p互质
        }
    }
}