题目描述

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

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

1.$x$和$a_0$的最大公约数是$a_1$；
2.$x$和$b_0$的最小公倍数是$b_1$。

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

Solve

1、

$gcd(x,a_0)=a_1$,$lcm(x,b_0)=b_1$。

2、

$gcd(x,a_0)=a_1=>gcd(x/a_1,a_0/a_1)=1$

3、

因为$gcd(a,b)*lcm(a,b)=a*b$
所以$gcd(x,b_0)*lcm(x,b_0)=x*b_0$
$gcd(x,b_0)=x*b_0/lcm(x,b_0)$
$gcd(x,b_0)=x*b_0/b_1$
$gcd(x*b_1,b_0*b_1)=x*b_0$
$gcd(b_1/b_0,b_1/x)=1$

4、

同时，$a_1|x,x|b_1$

这样就使需要判断的条件简单了一些，解法也就出来了。
枚举$b_1$的因数，然后判断是否符合结论。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n;
int a,b,c,d;
int ans;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int main()
{
	scanf("%d",&n);
	while(n--){
		ans=0;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		for(int x=1;x*x<=d;x++){
			int y=d/x;
			if(d%x!=0) continue;
			if(x%b==0&&gcd(x/b,a/b)==1&&gcd(d/c,d/x)==1) ans++;
			if(x==y) continue;
			if(y%b==0&&gcd(y/b,a/b)==1&&gcd(d/c,d/y)==1) ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
}