点击这里查看原题
贴一个杜教筛教程http://blog.csdn.net/skywalkert/article/details/50500009
预处理n^(2/3)+记忆化
注意虽然n的范围是2^31-1，没有爆int，但是n+1爆了，所以要用ll
/* User:Small Language:C++ Problem No.:2301 */ #include<bits/stdc++.h> #define ll long long #define inf 999999999 using namespace std; const int M=5e6; int cnt,prime[M]; bool not_prime[M]; map<int,ll> _phi,_mu; ll phi[M],mu[M]; ll calphi(ll n){ if(n<M) return phi[n]; map<int,ll>::iterator it; if((it=_phi.find(n))!=_phi.end()) return it->second; ll res=(ll)n*(n+1)/2; for(ll i=2,r;i<=n;i=r+1){ r=n/(n/i); res-=(r-i+1)*calphi(n/i); } return _phi[n]=res; } ll calmu(ll n){ if(n<M) return mu[n]; map<int,ll>::iterator it; if((it=_mu.find(n))!=_mu.end()) return it->second; ll res=1; for(ll i=2,r;i<=n;i=r+1){ r=n/(n/i); res-=(r-i+1)*calmu(n/i); } return _mu[n]=res; } void solve(){ int n; scanf("%d",&n); printf("%lld %lld\n",calphi(n),calmu(n)); } int main(){ freopen("data.in","r",stdin);// phi[1]=mu[1]=1; for(int i=2;i<M;i++){ if(!not_prime[i]){ prime[++cnt]=i; mu[i]=-1; phi[i]=i-1; } for(int j=1;j<=cnt&&i*prime[j]<M;j++){ not_prime[i*prime[j]]=1; if(i%prime[j]==0){ phi[i*prime[j]]=phi[i]*prime[j]; mu[i*prime[j]]=0; break; } phi[i*prime[j]]=phi[i]*phi[prime[j]]; mu[i*prime[j]]=-mu[i]; } } for(int i=1;i<M;i++){ phi[i]+=phi[i-1]; mu[i]+=mu[i-1]; } int t; scanf("%d",&t); while(t--) solve(); return 0; }