记录编号	233719	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]Hankson的趣味题	最终得分	100
用户昵称	农场主	是否通过	通过
代码语言	C++	运行时间	2.019 s
提交时间	2016-03-05 17:51:55	内存使用	2.30 MiB

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
bool p[100000+1000]={0};
int A0[100000]={0},A1[100000]={0},B0[100000]={0},B1[100000]={0},prime[100000]={0},tot=1,n,a0,a1,b0,b1;
void make();
int work(int a,int aa,int b,int bb);
void st(int x,int A[]);
void max(int l[],int r[]);
int gcd(int a,int b);
int main(){
	freopen("son.in","r",stdin);
	freopen("son.out","w",stdout);
	make();
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
		printf("%d\n",work(a0,a1,b0,b1));
	}
	return 0;
}
void st(int x,int A[]){
	int  t=x;
	for (int i=0;i<100000;i++) A[i]=0;
	for (int i=1;i<tot;i++){
		if (t<=1) break;
		while(t%prime[i]==0){
			t/=prime[i];
			A[i]++;
		}
	}
	if (t>1) A[0]=t;
	return;
}
void max(int l[],int r[]){
	if (l[0]==r[0]) l[0]=-l[0];
	else l[0]=l[0];
	for (int i=1;i<tot;i++){
		if (l[i]>r[i]) l[i]=l[i];
			else l[i]=-r[i];
	}
	return;
}
int work(int a,int aa,int b,int bb){
	st(aa,A0);
	st(a,A1);
	st(b,B0);
	st(bb,B1);
	max(B1,B0);
	int t=0,s=0;
	for (int i=1;i<tot;i++){
		if (B1[i]>0) for (int j=1;j<=B1[i];j++) t*=prime[i];
		if (B1[i]<0) for (int j=1;j<=-B1[i];j++) s*=prime[i];
		if (B1[0]>0) s*=B1[0];
		if (B1[0]<0) t*=B1[0];
	}
	s*=t;
	for (int i=0;i<tot;i++){
		if (A1[i]==A0[i]) A1[i]=0;
	}
	for (int i=1;i<tot;i++){
		if (A1[i]>0&&B1[i]>A0[i]) return 0;
	}
	if (A1[0]==B1[0]&&A1[0]!=0) return 0;
	if (s%aa!=0) return 0; 
	for (int i=1;i<tot;i++){
		if (B1[i]<0&&A0[i]>0) B1[i]+=A0[i];
	}
	for (int i=1;i<tot;i++){
		if (A1[i]>0&&B1[i]<0) B1[i]=0;
	}
	if (A0[0]>0||A1[0]>0) B1[0]=0;
	else if (B1[0]<0) B1[0]=-1;
	int num=1;
	for (int i=0;i<tot;i++){
		if (B1[i]<0) {
			num*=-1*B1[i]+1;
		}
	}
	return num;
}

void make(){
	for (int i=2;i<=(int)sqrt((double)2000000000);i++) if (!p[i]){
		prime[tot++]=i;
		for (int j=i*i;j<=(int)sqrt((double)2000000000);j+=i) p[j]=1;
	}		
}

int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}