首页 > > 程序设计 > C/C++ >

bzoj 2818 Gcd

2018-06-17 22:01:34来源：未知阅读 ()

传送门

这道题很巧妙

直接暴力的话毫无疑问是会gg的

Mathed:

若gcd（a,b）=p

则gcd（a/p,b/p）=1

那么枚举n以内的所有质数p

计算p以内所有互质的数（包括自己和自己）

加和即为答案

数对有序，因此要乘2

Code:

 1 #include<cstring>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<iostream>
 5 #define LL long long
 6 using namespace std;
 7 
 8 const int N=1e7;
 9 int n;
10 LL p[N+10],cnt=0,phi[N+10];
11 LL s[N+10];
12 bool vis[N+10];
13 LL ans=0;
14 
15 void pre(){
16     phi[1]=1;
17     for(int i=2;i<=n;++i){
18         if(!vis[i]){
19             p[++cnt]=i;
20             phi[i]=i-1;
21         }
22         for(int j=1;j<=cnt&&i*p[j]<=n;++j){
23             vis[i*p[j]]=1;
24             if(i%p[j]==0){
25                 phi[i*p[j]]=phi[i]*p[j];
26                 break;
27             }
28             phi[i*p[j]]=phi[i]*(p[j]-1);
29         }
30     }
31     for(int i=2;i<=n;++i) s[i]=s[i-1]+phi[i];//从 2 开始 
32 }
33 
34 int main(){
35     scanf("%d",&n);
36     pre();
37     for(int i=1;i<=cnt;++i){
38         if(n<2*p[i]) break;
39         ans+=2*s[n/p[i]];
40     }
41     ans+=cnt;
42     printf("%lld",ans);
43     return 0;
44 }