记录编号	81824	评测结果	AAAAAAAAEE
题目名称	[NOIP 2009]Hankson的趣味题	最终得分	80
用户昵称	ranto	是否通过	未通过
代码语言	C++	运行时间	1.508 s
提交时间	2013-11-18 19:02:21	内存使用	2.21 MiB

#include <fstream>
#include <cmath>

using namespace std;

ifstream in("son.in");
ofstream out("son.out");

typedef long long ull;

ull a,aa,b,bb;
ull prime[45000];

int main()
{
	int t;
	in>>t;
	prime[1]=2;
	prime[2]=3;
	int posi(3);
	for(int i=6;i<410000;i+=6)
	{
		ull temp(i-1);
		for(int j=1;prime[j]<static_cast<ull>(sqrt(temp))+1;++j)
		{
			if(temp%prime[j]==0)
			{
				goto ENDLOOP;
			}
		}
		prime[posi]=temp;
		++posi;
		ENDLOOP:
		temp=i+1;
		for(int j=1;prime[j]<static_cast<ull>(sqrt(temp))+1;++j)
		{
			if(temp%prime[j]==0)
			{
				goto ENDLOOP2;
			}
		}
		prime[posi]=temp;
		++posi;
		ENDLOOP2:;
	}
	/*for(int i=1;i!=4999;++i)
	{
		out<<prime[i]<<endl;
	}*/
	prime[posi]=-1;
	for(; t!=0; --t)
	{
		ull lpa(0), lpaa(0), lpb(0), lpbb(0);
		in>>a>>aa>>b>>bb;
		ull pa[50000]={0},paa[50000]={0},pb[50000]={0},pbb[50000]={0};
		int sa,saa,sb,sbb;
		posi=1;
		//out<<"a  :"<<endl;
		while(a!=1)
		{
			if(prime[posi]==-1)
			{
				lpa=a;
				break;
			}
			if(a%prime[posi]==0)
			{
				++pa[posi];
				a/=prime[posi];
				//out<<prime[posi]<<' ';
				continue;
			}
			posi++;
		}
		sa=posi;
		posi=1;
		//out<<endl<<"aa :"<<endl;
		while(aa!=1)
		{
			if(prime[posi]==-1)
			{
				lpaa=aa;
				break;
			}
			if(aa%prime[posi]==0)
			{
				++paa[posi];
				aa/=prime[posi];
				//out<<prime[posi]<<' ';
				continue;
			}
			posi++;
		}
		if(lpaa!=0&&lpa!=lpaa)
		{
			out<<0<<endl;
			continue;
		}
		saa=posi;
		posi=1;
		//out<<endl<<"b  :"<<endl;
		while(b!=1)
		{
			if(prime[posi]==-1)
			{
				lpb=b;
				break;
			}
			if(b%prime[posi]==0)
			{
				++pb[posi];
				b/=prime[posi];
				//out<<prime[posi]<<' ';
				continue;
			}
			posi++;
		}
		sb=posi;
		posi=1;
		//out<<endl<<"bb :"<<endl;
		while(bb!=1)
		{
			if(prime[posi]==-1)
			{
				lpbb=bb;
				break;
			}
			if(bb%prime[posi]==0)
			{
				++pbb[posi];
				bb/=prime[posi];
				//out<<prime[posi]<<' ';
				continue;
			}
			posi++;
		}
		if(lpb!=0&&lpb!=lpbb)
		{
			out<<0<<endl;
			continue;
		}
		//out<<endl;
		sbb=posi;
		ull x[10000]={0};
		ull y[10000]={0};
		if(sa==0)
		{
			goto JUMP1;
		}
		for(int i=1;i<sa+1;++i)
		{
			if(pa[i]>paa[i])
			{
				x[i]=(-paa[i])-1;//x[i]==paa[i]
				continue;
			}//pa[i]==paa[i]
			x[i]=pa[i];//x[i]>=pa[i]
		}
		JUMP1:
		/*for(int i=1;i!=sa+1;++i)
		{
			out<<x[i]<<' ';
		}
		out<<endl;*/
		if(sbb==0)
		{
			goto JUMP2;
		}
		for(int i=1;i<sbb+1;++i)
		{
			if(pbb[i]>pb[i])
			{
				y[i]=(-pbb[i])-1;//y[i]==paa[i]
				continue;
			}//pb[i]==pbb[i]
			y[i]=pbb[i];//0<=x[i]<=pbb[i]
		}
		JUMP2:
		/*for(int i=1;i!=sbb+1;++i)
		{
			out<<y[i]<<' ';
		}
		out<<endl;*/
		ull lmax(sa);
		if(sbb>sa)
		{
			lmax=sbb;
		}
		ull ret(1);
		for(ull i=1;i<lmax+1;++i)
		{
			if(x[i]<0)
			{
				if(y[i]<0)
				{
					if(x[i]!=y[i])
					{
						ret=0;
						break;
					}
				}
				else if(y[i]>=0)
				{
					if((-x[i]-1)>y[i])
					{
						ret=0;
						break;
					}
				}
			}
			else if(x[i]>=0)
			{
				if(y[i]<0)
				{
					if((-y[i]-1)<x[i])
					{
						ret=0;
						break;
					}
				}
				else if(y[i]>=0)
				{
					if(y[i]<x[i])
					{
						ret=0;
						break;
					}
					ret*=(y[i]-x[i]+1);
				}
			}
		}
		out<<ret<<endl;
	}
	return 0;
}