题目大意

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

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

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

题解

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

　　$$\because x \times b_{0} = \gcd(x, b_{0}) \times b_{1} \\ \therefore x = \frac{b_{1}}{b_{0}} \times \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 = ;

        for(int i = ; 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 << "\n";

    }

    return ;

}

参考程序

巴特西

【题解】Hankson 的趣味题

题目大意

题解

最新文章

热门文章