bzoj2818: Gcd懵逼乌斯反演

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,m,mu[10000001],f[10000001],p[10000001];bool o[10000001];
 4 int main()
 5 {
 6     scanf("%d",&n);
 7     mu[1]=1;
 8     for(int i=2;i<=n;i++)
 9     {
10         if(!o[i]) p[++m]=i,mu[i]=-1,f[i]=1;
11         for(int j=1;j<=m;j++)
12         if((long long)p[j]*i<=(long long)n)
13         {
14             o[p[j]*i]=1;
15             if(i%p[j]==0) f[p[j]*i]=mu[i];
16             else f[p[j]*i]=mu[i]-f[i];
17             if(i%p[j]==0) break;
18             mu[i*p[j]]=-mu[i];
19         }
20         else break;
21     }
22     long long ret=0;
23     for(int i=1;i<=n;i++)
24         ret+=(long long)(n/i)*(n/i)*f[i];
25     printf("%lld\n",ret);
26     return 0;
27 }