洛谷P2158 [SDOI2008]仪仗队

 1 //minamoto
 2 #include<cstdio>
 3 const int N=4e4+5;
 4 int vis[N],phi[N],p[N],m,ans;
 5 void init(int n=40000){
 6     phi[1]=1;
 7     for(int i=2;i<=n;++i){
 8         if(!vis[i]) p[++m]=i,phi[i]=i-1;
 9         for(int j=1;j<=m&&p[j]*i<=n;++j){
10             vis[i*p[j]]=1;
11             if(i%p[j]==0){
12                 phi[i*p[j]]=phi[i]*p[j];break;
13             }
14             phi[i*p[j]]=phi[i]*(p[j]-1);
15         }
16     }
17 }
18 int main(){
19     int n;scanf("%d",&n);init(n);
20     if(n==1) return puts("0"),0;
21     for(int i=1;i<n;++i) ans+=phi[i];
22     printf("%lld\n",(1ll*ans<<1)+1);
23     return 0;
24 }