今天在课堂上，老师讲解了如何求两个正整数 c1 和 c2 的最大公约数和最小公倍数。
现在 Hankson 认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数a0,a1,b0,b1，设某未知正整数 x 满足：
1． x 和 a0 的最大公约数是 a1；
2． x 和 b0 的最小公倍数是 b1。
Hankson 的“逆问题”就是求出满足条件的正整数 x。但稍加思索之后，他发现这样的 x 并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的 x 的个数。请你帮助他编程求解这个问题。
思路:把x分解为a*b,b0分解为a*c,则b1=a*b*c,b与c互素,b=b1/b0,我们可以枚举a的取值情况,得到一个x=a*b,然后再去判断gcd(x,a0)是否等于a1,想清楚就非常简单!
code:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 10001000; const int inf = 0x3f3f3f3f; const ll mod = 100000000; ll a0, a1, b0, b1; ll gcd(ll m, ll n) { return n == 0 ? m : gcd(n, m % n); } int main() { //freopen("test.txt", "r", stdin); int t; scanf("%d", &t); while (t--) { scanf("%lld%lld%lld%lld", &a0, &a1, &b0, &b1); ll b = b1 / b0; ll t = sqrt(b0); int ans = 0; for (int i = 1; i <= t; i++) { if (b0 % i == 0) {//找到一组a,b,即(i,b0/i); if (gcd(b, b0 / i) == 1&&gcd(i*b,a0)==a1) {//a=i ans++; } if (b0!=i*i&&gcd(b, i) == 1 && gcd((b0 / i) * b, a0) == a1) {//a=b0/i ans++; } } } printf("%d\n", ans); } return 0; }