记录编号	329338	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]Hankson的趣味题	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	2.179 s
提交时间	2016-10-25 08:52:08	内存使用	0.25 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define file(x) "son."#x
using std::min;
using std::max;
typedef long long ll;
const int P=5e4,UPB=45000,SZ=4700;
bool prime[P];
int n,pt[SZ],sz;
ll a0,a1,b0,b1,ans=1;
void calc(ll p){
	int ca0=0,ca1=0,cb0=0,cb1=0;
	while(a0%p==0) ca0++,a0/=p;
	while(a1%p==0) ca1++,a1/=p;
	while(b0%p==0) cb0++,b0/=p;
	while(b1%p==0) cb1++,b1/=p;
	int upb=1<<30,lwb=0;
	if(ca0==ca1) lwb=ca1;
	else upb=lwb=ca1; 
	if(cb0==cb1) upb=min(upb,cb1);
	else upb=min(upb,cb1),lwb=max(lwb,cb1);
	if(upb<lwb) ans=0;
	ans*=upb-lwb+1;
}
inline void solve(){
	ans=1;
	scanf("%lld%lld%lld%lld",&a0,&a1,&b0,&b1);
	for(int i=1;i<=sz&&ans;i++) calc(pt[i]);
	if(b1>1) calc(b1);
	if(a0>1) calc(a0);
	printf("%lld\n",ans);
}
int main(){
	freopen(file(in),"r",stdin);
	freopen(file(out),"w",stdout);
	memset(prime,1,sizeof(prime));
	for(int i=2;i<=UPB;i++) if(prime[i]) {
		pt[++sz]=i;
		for(int j=i+i;j<=UPB;j+=i) prime[j]=0;
	}
	scanf("%d",&n);
	while(n--) solve();
}