线性筛求欧拉函数

上节说道，求一个数的欧拉函数的时间复杂度等同于对其进行因式分解，都是

O(\sqrt N)

如果题目要求求某个区间上所有数的欧拉函数，再用这个方法的话，时间复杂度就是

O(N\sqrt N)

本节介绍用线性筛法求欧拉函数，他同样可以以线性(O(N))的时间复杂度解决上述问题 在此之前，先复习素数的线性筛法：

void get_primes(int n){//求n以内的所有素数
    for(int i=2;i<=n/i;i++){//sqrt,i*i的写法都不如这个好
        if(!v[i])   primes[++cnt]=i;
        for(int j=1;primes[j]<=n/i;j++){
            v[primes[j]*i]=true;
            if(i%primes[j]==0)  break;//因为这行，线性筛才是线性复杂度
        }
    }
}

在充分理解线性筛的条件下，给出欧拉函数的重要性质：

\phi(ab)=\frac{\phi(a) \phi(b) gcd(a,b)}{\phi(gcd(a,b))} 

这是由于欧拉函数是积性函数而得来的，具体证明从略，如果有机会专门写一篇 在这个式子中，包含了任意ab情况，我们现在观察线性筛法的内容：

1. 如果i是质数，显然phi(i)=i-1,这是因为除了他自己，任何比他小的正整数都和他互质
2. 如果i是合数，在线性筛法中，他会被筛去，而被筛的情况可以分为两种

对于我们将要筛去的数primes[j]*i:

1. 当i%primes[j]==0时： i是primes[j]的整数倍数，所以显然gcd(i,primes[j])=primes[j]所以 “`katex
   \phi(i\cdot primes[j])=\frac{\phi(i) \phi(primes[j]) gcd(i,primes[j])}{\phi(gcd(i,primes[j]))} \
   =\phi(i)\cdot primes[j]

2. 当i%primes[j]!=0时： 此时i和primes[j]是互质的，所以显然gcd(i,primes[j]=1)又因为primes[j]是质数，所以 “`katex
   \phi(i\cdot primes[j])=\phi(i)\cdot \phi(primes[j])=\phi(i) \cdot (primes[j]-1)

   
   
   至此，我们就解决了用线性筛质数求欧拉函数的问题

上源码了

int primes[N],cnt,phi[N];
bool v[N];
void get_phi(int n){
    phi[1]=1;//规定
    for(int i=2;i<=n;i++){
        if(!v[i]){
            primes[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;primes[j]<=n/i;j++){
            v[primes[j]*i]=true;
            if(i%primes[j]==0){
                phi[i*primes[j]]=phi[i]*primes[j];
                break;
            }
            phi[i*primes[j]]=phi[i]*(primes[j]-1);
        }
    }
}