记录编号	127476	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]Hankson的趣味题	最终得分	100
用户昵称	Cirno	是否通过	通过
代码语言	C++	运行时间	0.107 s
提交时间	2014-10-15 19:01:13	内存使用	0.51 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define SIZE 50000
#define ll long long
int p[SIZE];
ll a0,b0,a1,b1;
ll sum=1;
ll aa0,aa1,bb0,bb1;
ll low,high;
void getprime()
{
	bool prime[SIZE]={0};
	int k=0;
	int temp=(int)sqrt((double)SIZE);
	for(int i=2;i<SIZE;i++)
	{
		if(!prime[i])
		{
			p[k]=i,k++;
			if(i<=temp)
			{for(int j=i*i;j<=SIZE;j+=i) 
				prime[j]=1;}
		}
	}
}
ll resolve(ll &x,ll p)
{
	ll sum=0;
	while(x%p==0)
	{
		x/=p,sum++;
	}
	return sum;
}
void deal(ll pi)
{
	aa0=resolve(a0,pi),aa1=resolve(a1,pi),bb0=resolve(b0,pi),bb1=resolve(b1,pi);//素数的幂
	low=aa1,high=bb1;//π(bi-ai)
	if(aa0>aa1)//if(γi>βi)
		high=aa1;//(bi-ai)=1
	if(bb0<bb1)//if(γi<βi)
		low=bb1;//(bi-ai)=1
	{if(high>=low)
		sum*=(high-low+1);
	else
		sum=0;return;
	}
}
void init()
{
	freopen("son.in","r",stdin);
	freopen("son.out","w",stdout);
	int n;
	scanf("%d",&n);
	for(int k=0;k<n;k++)
	{	
		scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
		sum=1;
		for(int i=0;p[i]*p[i]<=b1&&p[i]!=0;i++)
		{
			deal(p[i]);
		}
		if(b1>1)
			deal(b1);
		printf("%d\n",sum);
	}
}
int main()
{
	getprime();
	init();
	return 0;
}