本文共 1791 字，大约阅读时间需要 5 分钟。
1 2 #include 3 #include 4 #include 5 #include 6 #include 7 #define ll long long 8 #define N 2000005 9 using namespace std;10 const int now=1<<20;11 ll phi[N];12 int pr[N],miu[N],su[N],tot;13 void yu()14 {15 phi[1]=1;16 miu[1]=1;17 for(int i=2;i<=now;i++)18 {19 if(!phi[i])20 {21 pr[i]=i;22 phi[i]=i-1;23 miu[i]=-1;24 su[++tot]=i;25 }26 for(int j=1;j<=tot&&su[j]<=pr[i]&&su[j]*i<=now;j++)27 {28 int p=su[j]*i;29 pr[p]=su[j];30 if(su[j]==pr[i])31 {32 phi[p]=phi[i]*su[j];33 miu[p]=0;34 }35 else36 {37 miu[p]=miu[i]*(-1);38 phi[p]=phi[i]*(su[j]-1);39 }40 }41 phi[i]+=phi[i-1];42 miu[i]+=miu[i-1];43 }44 return ;45 }46 map mp;47 int g(int x)48 {49 if(x<=now)return miu[x];50 if(mp.find(x)!=mp.end())return mp[x];51 int ans=0;int r=0;52 for(int l=2;l<=x;l=r+1)53 {54 r=x/(x/l);55 ans+=g(x/l)*(r-l+1);56 }57 ans=1-ans;58 return mp[x]=ans;59 }60 map mmp;61 ll f(int x)62 {63 if(x<=now)return phi[x];64 if(mmp.find(x)!=mmp.end())return mmp[x];65 ll ans=0;int r=0;66 for(int l=2;l<=x;l=r+1)67 {68 r=x/(x/l);69 ans+=f(x/l)*(r-l+1);70 }71 ans=(1+(ll)x)*(ll)x/2-ans;72 return mmp[x]=ans;73 }74 int main()75 {76 yu();77 int t;78 scanf("%d",&t);79 int n;80 while(t--)81 {82 scanf("%d",&n);83 if(n==2147483647)84 {85 puts("1401784457568941916 9569");86 continue;87 }88 ll ans2=g(n);89 ll ans1=f(n);90 printf("%lld %lld\n",ans1,ans2);91 }92 return 0;93 }
转载于:https://www.cnblogs.com/ezyzy/p/6414419.html