首页 > 代码库 > SPOJ 4491

SPOJ 4491

2024-07-25 14:08:50   220人阅读

不妨先把所有要求的素数的对的个数写出来

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


联系
我们