首页 > 代码库 > SPOJ 4491
SPOJ 4491
不妨先把所有要求的素数的对的个数写出来
f(2)=u(1)G(2)+u(2)*G(2*2)+u(3)*G(2*3)+.....u(k2)*G(2*k2)
f(3)=u(1)G(3)+u(2)*G(2*3)+u(3)*G(3*3)+.....u(k3)*G(3*k3)
....
f(p)=u(1)G(p)+u(2)*G(2*p)+u(3)*G(p*3)+.....u(kp)*G(p*kp)
相加之后
会发现,其实G的变量是从1~n的。于是,最重要便 是求出其合并后的系数了。怎么样求呢?我不懂,看了看别人的,发现竟有这样一个等式
于是,在线性筛选法上加上相关语句就可以求到相应的系数了。线性筛选:
http://wenku.baidu.com/link?url=ufaT0myBu70JxfkYUDsAtgPin6Y4uI8DwU43QCiQoqOOY9xhJJg3jr6DVn24sF2mAXRYrM6Hjrai-vMwfQ7-5IbQVDqwCGIwVzZR6xMVxiq
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define N 10000005using namespace std;typedef long long LL;bool check[N];int mu[N],tot;int prime[N],he[N];void initial(){ memset(check,false,sizeof(check)); memset(he,0,sizeof(he)); mu[1]=1; tot=0; for(LL i=2;i<N;i++){ if(!check[i]){ prime[tot++]=i; he[i]=1; mu[i]=-1; } for(LL j=0;j<tot;j++){ if(i*prime[j]>N) break; check[i*prime[j]]=true; if(i%prime[j]==0){ mu[i*prime[j]]=0; he[i * prime[j]] = mu[i]; break; } else{ he[i*prime[j]] = mu[i] - he[i]; mu[i*prime[j]]=-mu[i]; } } } for(int i=2;i<N;i++) he[i]+=he[i-1];}LL slove(int tx,int ty){ if(tx>ty) swap(tx,ty); int l=1,r,p1,p2; LL ans=0; while(l<=tx){ r=min(min(tx/(p1=tx/l),ty/(p2=ty/l)),tx); ans+=((LL) p1*(LL )p2*(LL )(he[r]-he[l-1])); l=r+1; } return ans;}int main(){ initial(); int T; scanf("%d",&T); int x,y,tx,ty; LL ans; while(T--){ scanf("%d%d",&x,&y); ans=slove(x,y); printf("%lld\n",ans); } return 0;}
SPOJ 4491
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。