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

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 2582 f(n)  

2014-02-21 17:29:12|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=2582
题意:
求f(n)= Gcd(3)+Gcd(4)+…+Gcd(i)+…+Gcd(n).
Gcd(n)=gcd(C[n][1],C[n][2],……,C[n][n-1]), C[n][i]表示从n件物品里选择i件的个数.
题解:
简单找规律,算出前10项的Gcd(i):
Gcd(3)=3,Gcd(4)=2,Gcd(5)=5,Gcd(6)=1,Gcd(7)=7,Gcd(8)=2,Gcd(9)=3,Gcd(10)=1
可以猜测有这样的规律:
如果i=p^k,p为质数,k为任意正整数,则Gcd(i)=p,否则Gcd(i)=1.
通过验证,发现规律正确.

LL ans[N+10];

bool f[N+10];
int tot,prime[N];

void Getprime()
{
int i,j,s;
memset(f,true,sizeof(f));
f[1]=false;
tot=0;
prime[tot++]=2;
for(i=4;i<N;i+=2)
f[i]=false;
for(i=3;i*i<=N;i+=2)
{
if(!f[i])
continue;
prime[tot++]=i;
for(s=2*i,j=i*i;j<N;j+=s)
f[j]=false;
}
for(;i<N;i++)
if(f[i])
prime[tot++]=i;
}


void init()
{
for(int i=3;i<=N;i++)
ans[i]=1;
for(int i=0;i<tot;i++)
for(LL j=prime[i];j<=N;j=j*prime[i])
ans[j]=prime[i];
ans[0]=ans[1]=ans[2]=0;
for(int i=3;i<=N;i++)
ans[i]+=ans[i-1];
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testout.txt","w",stdout);
#endif
Getprime();
init();
int n;
while(sf(n)!=EOF)
pf64(ans[n]);
return 0;
}


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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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