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 10000005

using 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

最新文章

热门文章