P1072 Hanson 的趣味题
题目描述
Hanks 博士是 BT(Bio-Tech，生物技术) 领域的知名专家，他的儿子名叫 Hanson。现在，刚刚放学回家的 Hanson 正在思考一个有趣的问题。
今天在课堂上，老师讲解了如何求两个正整数(c_1) 和 (c_2) 的最大公约数和最小公倍数。现在 Hanson 认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数(a_0,a_1,b_0,b_1)，设某未知正整数(x)满足：
1． (x) 和 (a_0) 的最大公约数是 (a_1)；
2． (x)和 (b_0) 的最小公倍数是(b_1)。
Hanson 的“逆问题”就是求出满足条件的正整数(x)。但稍加思索之后，他发现这样的(x)并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的(x)的个数。请你帮助他编程求解这个问题。
输入格式
第一行为一个正整数 (n)，表示有 (n) 组输入数据。接下来的(n)行每行一组输入数据，为四个正整数 (a_0,a_1,b_0,b_1)，每两个整数之间用一个空格隔开。输入数据保证 (a_0)能被 (a_1) 整除，(b_1) 能被(b_0)整除。
输出格式
共(n)行。每组输入数据的输出结果占一行，为一个整数。
对于每组数据：若不存在这样的(x)，请输出 (0)；
若存在这样的(x)，请输出满足条件的(x) 的个数；
输入输出样例
输入 #1
2
41 1 96 288
95 1 37 1776
输出 #1
6
2
说明/提示
【说明】
第一组输入数据，(x)可以是$ 9,18,36,72,144,288$，共有(6)个。
第二组输入数据，(x) 可以是(48,1776)共有(2)个。
【数据范围】
对于 50%的数据，保证有 (1≤a_0,a_1,b_0,b_1≤10000) 且(n≤100)。
对于 100%的数据，保证有 (1≤a_0,a_1,b_0,b_1≤2,000,000,000) 且 (n≤2000)。
题解
分析
枚举(x)，使得满足第一个条件，由此可以推出。
同理
整合，得出
于是，我们先用(2log(n))的算法暴力枚举因数，然后判断2次(gcd)就可以了。
代码
#include<bits/stdc++.h>
using namespace std;
inline int gcd(int a,int b) {
return b==0?a:gcd(b,a%b);
}
int T,a1,a2,b1,b2,op,ans;
int main(){
read(T);
while(T--){
ans=0;
read(a1),read(a2),read(b1),read(b2);
op=sqrt(b2);
for(int i=1;i<=op;i++){
if(b2%i==0){
if(i%a2==0&&gcd(i/a2,a1/a2)==1&&gcd(b2/b1,b2/i)==1) ans++;
int y=b2/i;
if(i==y) continue;
if(y%a2==0&&gcd(y/a2,a1/a2)==1&&gcd(b2/b1,b2/y)==1) ans++;
}
}
cout<<ans<<endl;
}
return 0;
}