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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

【数论水题】Bzoj2190: [SDOI2008]仪仗队  

2014-04-11 10:07:11|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

@[SDOI2008]仪仗队

画图后会发现,一个点看不见,说明它的前方有一个点挡住。

如果能看到的点A为(x,y),那么看不到的点B(被该点挡住)一定为(Cx,Cy)(c>1&&c属于整数)

所以这样题目就变成了找一个点(a,b)  (0<=a&b<n)  符合gcd(a,b)=1求这样的点的个数

一个点的坐标一定有a,b互质,也就是没有质因数

那么我们就可以先得到一个<n的素数的集合

然后让a从集合里选走一些元素,(每个元素的个数可以乘一个常数)然后让b从集合里选一些元素,求一下选法的个数

于是就成了集合选数方案数问题……

然后我就傻逼了。

感谢Gty神犇的提醒……

实际上……只要考虑a>b的情况枚举一下a,对于每个a求Phi(b的个数),对这个值 *2+3就行了……

代码

/*
仪仗队
0<=a,b<n
gcd(a,b) ==1
求个数
*/
#include<cstdio>
typedef long long LL ;
const int N = 60000+1;
int n,m,pri[N];
LL ans,phi[N];
short v[N];
void getphi(){
int i,j;
for(i=2;i<=n;i++){
if(!v[i]){
pri[++pri[0]] = i;
phi[i] = i-1;
}
for(j=1;j<=pri[0]&&pri[j]*i<=n;j++){
v[pri[j]*i] = 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;
scanf("%d",&n);
getphi();
for(i=1;i<n;i++)
ans+=phi[i];
printf("%lld",ans*2+3);
return 0;
}



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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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