@[mona](/space/show?uid=66636)
筛到$4e6$就能过了
by kraylas @ 2018-12-30 09:11:23
@[花_Q](/space/show?uid=87940)
$4e6$还是挂了。
甚至更慢。
by mona @ 2018-12-30 09:26:58
@[mona](/space/show?uid=66636)
我用的map好像多个log
但是能过23333
```
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
const int maxn = 4e6+5;
int mian(){
int s=0,f=1;char ch;
while(!isdigit(ch=getchar()))(ch=='-')&&(f=-1);
for(s=ch-'0';isdigit(ch=getchar());s=s*10+ch-'0');
return s*f;
}
bool vis[maxn];
int p[maxn],pcnt;
long long phi[maxn];
int mu[maxn];
map<int,int>s_mu;
map<int,long long>s_phi;
void prev(){
phi[1]=1;mu[1]=1;
for(int i=2;i<=4e6;++i){
if(!vis[i])p[++pcnt]=i,mu[i]=-1,phi[i]=i-1;
for(int j=1;j<=pcnt&&p[j]*i<=4e6;++j){
vis[i*p[j]]=1;
if(i%p[j]==0){
mu[i*p[j]]=0;
phi[i*p[j]]=p[j]*phi[i];
break;
}
mu[i*p[j]]=-mu[i];
phi[i*p[j]]=phi[i]*(p[j]-1);
}
mu[i]+=mu[i-1];
phi[i]+=phi[i-1];
}
}
int S_MU(int n){
if(n<=4e6)return mu[n];
if(s_mu.count(n))return s_mu[n];
int ans=1;
for(int l=2,r;l<=n;l=r+1){
r=n/(n/l);
ans-=(r-l+1)*S_MU(n/l);
}
return s_mu[n]=ans;
}
long long S_PHI(int n){
if(n<=4e6)return phi[n];
if(s_phi.count(n))return s_phi[n];
long long ans=1LL*n*(n+1)/2;
for(int l=2,r;l<=n;l=r+1){
r=n/(n/l);
ans-=(r-l+1)*S_PHI(n/l);
}
return s_phi[n]=ans;
}
int main(){
int T=mian();
prev();
while(T--){
int n=mian();
cout<<S_PHI(n)<<' '<<S_MU(n)<<endl;
}
return 0;
}
```
by kraylas @ 2018-12-30 10:02:41
unordered_map
by yuzhechuan @ 2019-07-16 09:24:55