题解：P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题

· · 题解

题意

题目给定两个正整数 x 和 y ，要求找到所有满足以下条件的正整数对 (a, b) ：

  1. \gcd(a, b) = x
  2. \text{lcm}(a, b) = y

其中， \gcd(a, b) 表示 a 和 b 的最大公约数， \text{lcm}(a, b) 表示 a 和 b 的最小公倍数。

思路

首先，我们需要理解最大公约数和最小公倍数之间的关系。对于任意两个正整数 a 和 b ，有以下关系式：

\gcd(a, b) \times \text{lcm}(a, b) = a \times b

根据题目条件， \gcd(a, b) = x 且 \text{lcm}(a, b) = y ，因此可以得到：

x \times y = a \times b

也就是说， a \times b = x \times y 。我们可以将 a 和 b 表示为：

a = x \times k, \quad b = x \times m

其中 k 和 m 是互质的正整数（即 \gcd(k, m) = 1 ），因为 \gcd(a, b) = x 。

将 a 和 b 代入 a \times b = x \times y ，得到：

(x \times k) \times (x \times m) = x \times y \implies x^2 \times k \times m = x \times y \implies k \times m = \frac{y}{x}

因此，我们需要找到所有满足 k \times m = \frac{y}{x} 且 \gcd(k, m) = 1 的正整数对 (k, m) 。

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll gcd(ll x, ll y)
{
    if (y == 0)
    {
        return x;
    }
    return gcd(y, x % y);
}

int main()
{
    ll x, y, cnt = 0;
    cin >> x >> y;
    ll t = x * y;
    for (ll i = 1; i <= sqrt(t); i++)
    {
        if (t % i == 0 && gcd(i, t / i) == x)
        {
            cnt += 2;
            if (i * i == t) cnt--;
        }
    }
    cout << cnt << endl;
    return 0;
}