大佬教程收集整理的这篇文章主要介绍了[bzoj3944]Sum,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
1 #include<bits/stdc++.h> 2 #include<tr1/unordered_map> 3 using namespace std; 4 #define ll long long 5 #define N 5000005 6 int t,n,mu[n],vis[n],p[n]; 7 ll cp[n]; 8 tr1::unordered_map<int,ll>@H_503_34@m1; 9 tr1::unordered_map<int,int>@H_503_34@m2; 10 ll djs_cp(int n){ 11 if (n<=N-5)return cp[n]; 12 if (m1[n])return m1[n]; 13 ll ans=(n+1LL)*n/2; 14 for(int i=2,j;;i=j+1){ 15 j=n/(n/i); 16 ans-=djs_cp(n/i)*(j-i+1); 17 if (j==n)return m1[n]=ans; 18 } 19 } 20 int djs_mu(int n){ 21 if (n<=N-5)return mu[n]; 22 if (m2[n])return m2[n]; 23 int ans=1; 24 for(int i=2,j;;i=j+1){ 25 j=n/(n/i); 26 ans-=djs_mu(n/i)*(j-i+1); 27 if (j==n)return m2[n]=ans; 28 } 29 } 30 int main(){ 31 mu[1]=cp[1]=1; 32 for(int i=2;i<=N-5;i++){ 33 if (!vis[i])cp[i]=i+(mu[p[++p[0]]=i]=-1); 34 for(int j=1;(j<=p[0])&&(i*p[j]<=N-5);j++){ 35 vis[i*p[j]]=1; 36 if (i%p[j]==0){ 37 cp[i*p[j]]=cp[i]*p[j]; 38 break; 39 } 40 mu[i*p[j]]=-@H_503_34@mu[i]; 41 cp[i*p[j]]=cp[i]*(p[j]-1); 42 } 43 } 44 for(int i=2;i<=N-5;i++){ 45 mu[i]+=mu[i-1]; 46 cp[i]+=cp[i-1]; 47 } 48 scanf("%d",&t); 49 while (t--){ 50 scanf("%d",&n); 51 printf("%lld %d\n",djs_cp(n),djs_mu(n)); 52 } 53 }
以上是大佬教程为你收集整理的[bzoj3944]Sum全部内容,希望文章能够帮你解决[bzoj3944]Sum所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。