Bzoj 2818: Gcd 莫比乌斯,分块,欧拉函数,线性筛

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define LL long long
 4 #define MAXN 10000010
 5 int prime[670010],mu[MAXN],qz[MAXN],tot,N;
 6 bitset<MAXN> vis;
 7 int read()
 8 {
 9     int s=0,fh=1;char ch=getchar();
10     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)fh=-1;ch=getchar();}
11     while(ch>=‘0‘&&ch<=‘9‘){s=s*10+(ch-‘0‘);ch=getchar();}
12     return s*fh;
13 }
14 void getmu()
15 {
16     int i,j;
17     mu[1]=1;
18     tot=0;
19     for(i=2;i<=N;i++)
20     {
21         if(vis[i]==0)
22         {
23             prime[++tot]=i;
24             mu[i]=-1;
25         }
26         for(j=1;j<=tot&&prime[j]*i<=N;j++)
27         {
28             vis[prime[j]*i]=1;
29             if(i%prime[j]==0)
30             {
31                 mu[i*prime[j]]=0;
32                 break;
33             }
34             mu[i*prime[j]]=-mu[i];
35         }
36     }
37 }
38 void Qz()
39 {
40     for(int i=1;i<=N;i++)qz[i]=qz[i-1]+mu[i];
41 }
42 LL calc(int n)
43 {
44     int d,pos;
45     LL sum=0;
46     for(d=1;d<=n;d=pos+1)
47     {
48         pos=n/(n/d);
49         sum+=(LL)(n/d)*(n/d)*(qz[pos]-qz[d-1]);
50     }
51     return sum;
52 }
53 int main()
54 {
55     int i;
56     LL ans=0;
57     N=read();
58     getmu();
59     Qz();
60     for(i=1;i<=tot&&prime[i]<=N;i++)ans+=calc(N/prime[i]);
61     printf("%lld",ans);
62     fclose(stdin);
63     fclose(stdout);
64     return 0;
65 }