Luogu P1072 Hankson 的趣味题

题目大意

　　已知正整数$a_{0}$、$a_{1}$、$b_{0}$、$b_{1}$（$1 leq a_{0}, a_{1}, b_{0}, b_{1} leq 2 imes 10^{9}$），设某未知正整数$x$满足：

1.  $x$和$a_{0}$的最大公约数是$a_{1}$；
   
2.  $x$和$b_{0}$的最小公倍数是$b_{1}$。

　　请你求出有多满足条件的$x$。

题解

　　方法有很多，这里给一种比较暴力的解法。

　　$$ecause  x imes b_{0} = gcd(x, b_{0}) imes b_{1} \ herefore x = frac{b_{1}}{b_{0}} imes gcd(x, b_{0})$$

　　我们只需要用$O(sqrt{b_{0}})$的时间枚举$gcd(x, b_{0})$，然后判断是否满足条件即可。

#include <iostream>

using namespace std;

int n;
int a0, a1, b0, b1;
int ans;

int gcd(int a, int b)
{
    int c;
    while(b)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

long long lcm(int a, int b)
{
    return (long long)a * b / gcd(a, b);
}

int main()
{
    cin >> n;
    int x;
    while(n--)
    {
        cin >> a0 >> a1 >> b0 >> b1;
        ans = 0;
        for(int i = 1; i * i <= b0; ++i)
        {
            if(b0 % i) continue;
            x = b1 / b0 * i;
            if(gcd(x, a0) == a1 && lcm(x, b0) == b1) ++ans;
            if(b0 / i == i) continue;
            x = b1 / b0 * b0 / i;
            if(gcd(x, a0) == a1 && lcm(x, b0) == b1) ++ans;
        }
        cout << ans << "
";
    }
    return 0;
}