POJ 2478：Farey Sequence

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 <cstdio>
 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<k&&prime[j]*i<=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
",pre[n]);
31     }
32 }