BZOJ 2818 gcd（莫比乌斯反演）

#include<cstdio> #include<algorithm> #include<iostream> #include<cmath> #include<cstring> #include<vector> #define ll long long #define N 10000010 using namespace std; bool check[N+10]; int prime[N]; int mu[N+10]; int tot; int n; void Moblus() { memset(check,0,sizeof check); mu[1]=1; tot=0; for(int i=2; i<N; i++) { if(!check[i]) { prime[tot++]=i; mu[i]=⑴; } for(int j=0; j<tot; j++) { if(i*prime[j]>N)break; check[i*prime[j]]=1; if(i%prime[j]==0) { mu[i*prime[j]]=0; break; } else mu[i*prime[j]]=-mu[i]; } } } int main() { Moblus(); while(scanf("%d",&n)!=EOF) { ll ans=0; for(int i=0; i<tot; i++) { int x=n/prime[i]; if(x==0)break; for(int j=1; j<=x; j++) ans+=(ll)mu[j]*(x/j)*(x/j); } printf("%lld ",ans); } return 0; }