记录编号	429953	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]Hankson的趣味题	最终得分	100
用户昵称	swttc	是否通过	通过
代码语言	C++	运行时间	2.192 s
提交时间	2017-07-28 21:28:44	内存使用	3.37 MiB

#include<iostream>
#include<cstdio>
#define LL long long

using namespace std;

LL n,p[200010],f[200010],a,aa,b,bb,m,pc;

void shaisu()
{
	for(int i=2;i<=50000;i++)
	{
		if(!f[i])
		{
			p[++pc]=i;
			f[i]=1;
		}
		for(int j=1;j<=pc;j++)
		{	
			if(i*p[j]>50000) break;
			f[p[j]*i]=1;
			if(i%p[j]==0)
			 break;
		}
	}
}

LL fenjie()
{
	LL t=1;
	for(int i=1;i<=pc;i++)
	{
		if(p[i]>m) break;
		LL ca=0,caa=0,cb=0,cbb=0;
		while(a%p[i]==0&&a)
		{
			ca++;
			a/=p[i];
		}
		while(aa%p[i]==0&&aa)
		{
			caa++;
			aa/=p[i];
		}
		while(b%p[i]==0&&b)
		{
			cb++;
			b/=p[i];
		}
		while(bb%p[i]==0&&bb)
		{
			cbb++;
			bb/=p[i];
		}
		if(caa>ca||cbb<cb)
		{
			return -1;
		}
		if(min(ca,caa)>max(cb,cbb))
		{
			return -1;
		}//cout<<ca<<" "<<caa<<" "<<cb<<" "<<cbb<<endl;
		if(cb<cbb&&ca>caa&&caa!=cbb) return -1;
		if(cb<cbb||ca>caa) continue;
		t*=max(cb,cbb)-min(ca,caa)+1;//cout<<t<<" ";
	}
	return t;
}

int main()
{
	freopen("son.in","r",stdin);
	freopen("son.out","w",stdout);
	shaisu();
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d%d",&a,&aa,&b,&bb);
		m=max(max(a,aa),max(b,bb));
		int t=fenjie();
		int ff=0;
		if(a!=1)
		{
			p[++pc]=a;
			ff=1;
		}
		if(bb!=1)
		{
			p[++pc]=bb;
			ff=1;
		}
		if(ff)
		 t*=fenjie();
		if(t<0) cout<<0<<endl;
		else cout<<t<<endl;
	}
	return 0;
}