bzoj 2818 Gcd

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

新老客户大回馈,云服务器低至5折

传送门


这道题很巧妙

直接暴力的话毫无疑问是会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 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:最短路径算法

下一篇:八数码问题:bfs及dbfs版本详解