跳转到在线页面

Description

Hanks博士是BT（Bio-Tech，生物技术）领域的知名专家，他的儿子名叫Hankson。现在，刚刚放学回家的Hankson正在思考一个有趣的问题。

　　今天在课堂上，老师讲解了如何求两个正整数c1和c2的最大公约数和最小公倍数。现在 Hankson认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数 a0,a1,b0,b1，设某未知正整数x满足：

　　1、x和a0的最大公约数是a1；

　　2、x和b0的最小公倍数是b1。

　　Hankson的“逆问题”就是求出满足条件的正整数x。但稍加思索之后，他发现这样的x并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的x的个数。请你帮助他编程求解这个问题。

Input

第一行为一个正整数n，表示有n组输入数据。接下来的n行每行一组输入数据，为四个正整数a0，a1，b0，b1，每两个整数之间用一个空格隔开。输入数据保证a0能被a1整除，b1能被b0整除。

Output

共n行。每组输入数据的输出结果占一行，为一个整数。　　对于每组数据：若不存在这样的x，请输出0；　　若存在这样的x，请输出满足条件的x的个数；

Sample Input

1
2
3
2
41 1 96 288
95 1 37 1776

Sample Output

1
2
6
2

Hint

1
对于50%的数据，保证有1≤a0，b1，b0，b1≤10000且n≤100。对于100%的数据，保证有1≤a0，b1，b0，b1≤2,000,000,000且n≤2000。

分析

两个数的乘积等于这两个数的最大公约数与最小公倍数的乘积

——百度热心网友

首先由：

可知x是b1的一个因子且为a1倍数，因而从1到sqrt(b1)枚举每个整除b1的数字，若其是a1的整数倍，且满足上述二式则ans+1
暴力枚举在一中OJ上可以得90分…

100分解法还要推出更深的结论：

则：

进一步的我们有：

设置几个辅助变量：

考虑gcd(s/p,n)=1要满足s/p与n没有公共质因数，因此我们需要将s/p与n的公共质因数筛去，得到满足条件的数T，T是s/p的某个因数

又因为gcd(p,m)=1，而s/p=Tr(r为整数)，那么p=s/(T*r)，则gcd(s/(T*r),n)=1，利用刚才方法将两者的公共质因数筛去得到S，那么S的因数个数就是答案

Codes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// hankson 趣味题 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a0,a1,b0,b1,ans;
LL gcd(LL a,LL b)
{
	if(a<b) swap(a,b);
	return b==0?a:gcd(b,a%b);
}
inline LL lcm(LL a,LL b)
{
	return a*b/gcd(a,b);
}
inline LL seprate(LL a,LL b)
{
	LL S=sqrt(b);
	for(LL i=2;i<=S;i++){
		if(b%i==0)
			while(a%i==0) a/=i;
		while(b%i==0) b/=i;
	}
	if(b!=1) while(a%b==0) a/=b;
	return a;
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("testin.txt","r",stdin);
	freopen("testout.txt","w",stdout);
	#endif
	int T;
	cin>>T;
	while(T--){
		cin>>a0>>a1>>b0>>b1;
		ans=0;
		LL m=a0/a1,n=b1/b0,s=b1/a1;
		LL tmp1=seprate(s,n);
		if(gcd(s/tmp1,m)!=1) cout<<0<<'\n';
		else{
			LL tmp2=seprate(tmp1,m);
			LL S=sqrt(tmp2);
			for(LL i=1;i<=S;i++)
				if(tmp2%i==0)
					ans+=(tmp2/i==i)?1:2;
			cout<<ans<<'\n';
		}
	}
	return 0;
}