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

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

SPOJ PGCD  

2010-09-02 14:50:03|  分类: spoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目求1<=i<=a,1<=j<=b,gcd(i,j)是素数的有多少个,先考虑一个简单的问题,就是这其中gcd是1的有多少个,考虑函数f(a,b,k)表示1到a,1到b之间最大公约数是k的倍数的数有多少个,g(a,b,k)表示最大公约数是k的有多少个那么即使求g(a,b,1)并且知道,f是g的和函数,并且是整数因子格整除关系的和函数,且知道f(a,b,k)=floor(a/k)*floor(b/k)所以可以利用莫比乌斯反演,用在整数因子格上的莫比乌斯函数来求解
回到刚才的问题,一种简单的想法就是枚举素数p,不断除p,然后把最大公约数1的加起来,注意到一个问题,枚举2时求gcd=1时可能要再除以3,而枚举3时求gcd=1时要除以2,有重复所以可以记录,在求莫比乌斯函数的时候可以记录总共会重复几次就可以了,然后就是。。。。。。。。。。面对恶心的spoj的各种常数优化。。。后来发现在求gcd=1时由于f(a,b,k)=floor(a/k)*floor(b/k)注意到很多时候floor(a/k)=floor(a/(k+1))这样可以一次性计算,减少很多时间,然后终于内牛满面的ac此题。。。
#include<cstdio>
#define min(a,b) (a<b?a:b)
const int m=10000010;
char a[m],b[m],c[m];
int a1,a2,n,k,t,d[m],mm,m1,m2,k1,k2;
int main(){
for(int i=2;i<m;++i){
if(!a[i]){
for(int j=i;j<m;j+=i)
++a[j];
if(i<3165){
k=i*i;
for(int j=k;j<m;j+=k)
++b[j];
}
if(i<217){
k=i*i*i;
for(int j=k;j<m;j+=k)
++b[j];
}
}
d[i]=d[i-1];
if(c[i]||b[i]-1>0)
continue ;
if(b[i]){
if(a[i]%2)
k=-1;
else k=1;
}else{
if(a[i]%2)
k=a[i];
else k=-a[i];
}
d[i]+=k;
}
scanf("%d",&t);
while(t--){
scanf("%d%d",&a1,&a2);
if(a1>a2){
int tmp=a1;
a1=a2;
a2=tmp;
}
long long ans=0;
for(int i=1;i<a1;i=mm){
k1=a1/(i+1);
k2=a2/(i+1);
m1=a1/k1;
m2=a2/k2;
mm=(m1<m2?m1:m2);
ans+=(long long)k1*k2*(d[mm]-d[i]);
}
printf("%lld\n",ans);
}
return 0;
}
  评论这张
 
阅读(588)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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