题目
bzoj第一题，竟然不是1000，233，自己也是可以的。。
经典莫比乌斯反演。。。
#include<iostream> #include<algorithm> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #define MAXN 10000000 #define LL long long using namespace std; bool P[MAXN+1],flag; int mu[MAXN+1]; char s[21]; LL len; LL x,y; LL prime[MAXN+1],size; LL N; LL ans; void write(int x) { len=0; flag=true; if(x<0)flag=false,x=-x; if(x==0)putchar('0'); while(x!=0) { s[++len]=x%10+'0'; x=x/10; } if(!flag)putchar('-'); for(int i=len;i>=1;i--) putchar(s[i]); putchar('\n'); } int main() { scanf("%d",&N); memset(P,true,sizeof(P)); P[1]=false; for(LL i=2;i<=N;i++) { if(P[i]) { { for(LL j=i*i;j<=N;j+=i) P[j]=false; } } } for(LL i=1;i<=N;i++) mu[i]=1; for(LL i=2;i<=N;i++) { if(P[i]) { mu[i]=-1; for(LL j=i+i;j<=N;j+=i) { if((j/i)%i==0)mu[j]=0; else mu[j]=-mu[j]; } } } size=0; for(LL i=1;i<=N;i++) { if(P[i]) prime[++size]=i; } ans=0; for(LL i=1;i<=size;i++) { for(LL j=1;j<=N/prime[i];j++) ans=ans+mu[j]*(N/(j*prime[i]))*(N/(j*prime[i])); } cout<<ans; return 0; }