POJ 2478：Farey Sequence

题目链接：

题目大意：求$\sum_{i=2}^n \varphi(i)$.

线性筛

根据$\varphi(n)=n \prod_{i=1}^n(1- \frac{1}{p_i})$公式，可以在$O(n)$的复杂度下求出所有$\varphi(n)$的值.

同理，极性函数都可以用线性筛求得.

代码如下：

1 #include 
     
       2 #define N 1000005 3 using namespace std; 4 typedef long long ll; 5 ll ver[N],pre[N],prime[N],k; 6 bool vis[N]={
   1,1}; 7 void init(){ 8     for(int i=2;i<=1000000;++i){ 9         if(!vis[i]){10             prime[k++]=i;11             ver[i]=i-1;12         }13         for(int j=0;j
      
       <=1000000;++j){14             vis[prime[j]*i]=1;15             if(i%prime[j]==0){16                 ver[prime[j]*i]=ver[i]*prime[j];17                 break;18             }19             ver[prime[j]*i]=ver[i]*(prime[j]-1);20         }21     }22     for(int i=1;i<=1000000;++i)23         pre[i]=pre[i-1]+ver[i];24 }25 int main(void){26     init();27     int n;28     while(scanf("%d",&n)){29         if(n==0)break;30         printf("%lld\n",pre[n]);31     }32 }