注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2818]Gcd  

2014-10-17 11:41:54|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
上个学期省选的时候就看着道题了……当时太弱怎么也不会。

现在终于A掉了QuQ

题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
int scan(){int i=0;scanf("%d",&i);return i;}
typedef long long LL;
const int N= 1E7+10;
int phi[N],pri[N],n;
LL sum[N];
short v[N];
void getpri(){
int nn=n;
for(int i=2;i<=nn;i++){
if(!v[i]){
pri[++pri[0]] = i;
phi[i] = i-1;
}
for(int j=1;(LL)i*pri[j]<=nn&&j<=pri[0];j++){
v[i*pri[j]] = 1;
if(i%pri[j] ==0){
phi[i*pri[j]] = phi[i]* pri[j];
break;
}else{
phi[i*pri[j]] = phi[i]*(pri[j]-1);
}
}
}
}
int main(){
int i,j,a;
n = scan();
getpri();
for(i=1;i<=n;i++)sum[i] = phi[i] + sum[i-1];
LL ans=0;
for(i=1;i<=pri[0];i++)
ans += sum[n/pri[i]]*2 + 1;
cout<<ans<<endl;
return 0;
}

题解:

题目要求gcd为质数的数对个数,那么这个数对必然有同除一个质数后互质,所以利用欧拉函数

先处理一个前缀和sum,然后枚举每个质数pri[i],答案就是Σsum[n/pri[i]]*2 + 1

  评论这张
 
阅读(11)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017