我也是只会做这种题了囧……
仔细分析这个图，手画几个N，就能得出规律……
ans(n)+1=sigma(phi[i])(i=2...n-1)
于是代码就出来了……线筛phi谁不会……
#include<cstdio>
int n,eu[400005],ans=2;
void E(){
for(int i=1;i<=400000;i++)eu[i]=i;
for(int i=2;i<=400000;i++){
if(eu[i]==i){
for(int j=i;j<=400000;j+=i){
eu[j]=eu[j]/i*(i-1);
}
}
}
}
int main(){
freopen("2190.in","r",stdin);
freopen("2190.out","w",stdout);
scanf("%d",&n);
E();
for(int i=2;i<n;i++)ans+=eu[i];
printf("%d\n",ans*2-1);
return 0;
}
评论 (0)
