xumOJ 1447 積性函數

[cpp]   /*    xmu 1447 積性函數   題解：當 (a,b)=1; 則 f(a*b)=f(a)*f(b);  x[i] 表示歐拉函數  sum[i] 表示因子個數  p[i] 表示第 i 個素數      */   #include<iostream>     #include<cstdio>     #include<cmath>     #include<algorithm>     #define manx 1000001     using namespace std;     int x[manx],sum[manx],p[manx];     bool s[manx];          void prime(){         int num=0;         for(int i=0;i<manx;i++) s[i]=0,x[i]=0,sum[i]=1,p[i]=0;         for(int i=2;i*i<manx;i++){             if(!s[i]){                 p[num++]=i;                 for(int j=2;j*i<manx;j++)                     s[i*j]=1;             }         }         for(int i=2;i<manx;i++)              if(!s[i]) p[num++]=i;     }          void oula(){         for(int i=2; i<manx;i++){             if(!s[i]){                 x[i]=i-1;                 sum[i]=2;                 continue;             }             for(int j=0;p[j]*p[j]<=i;j++){                 if(i%p[j]==0){                    if(i/p[j]%p[j]){  ////只有一個p[j]素數因子                       sum[i]=sum[i/p[j]]*2;                           x[i]=x[i/p[j]]*x[p[j]];                   }                   else {   ////////可能有多個 p[i]的素數因子                        int ans = i;                        x[i]=x[i/p[j]]*p[j];                       while(ans%p[j]==0) ans/=p[j]; ///明白這段還是需要組合數學知識的                        sum[i]=sum[ans]+sum[i/p[j]];  ///更新 i 的因子個數                    }                   break; ///// 處理完跳出循環                }               }       }     }          int main(){         prime();         oula();         int t,n;         scanf("%d",&t);         while(t--){             scanf("%d",&n);             printf("%d\n",n-sum[n]-x[n]+1);         }     }