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

S_Y_B_S · 2025-02-12 14:09:00 · 题解

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

前置芝士

最大公约数 \gcd，这里提供一种参考写法（当然你也可以用内置函数__gcd()）：

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

以及最小公倍数 \operatorname{lcm}（当然本题也可以不求 \operatorname{lcm}，后面会说到）：

int lcm(int a, int b)
{
    return a / gcd(a, b) * b;
    //这里先除再乘是好习惯，避免溢出
}

思路

本题我们可以利用关于最大公约数与最小公倍数的小小的性质，即：

所以，对于任意一组合法的 p,q，一定有 xy=pq。

然后我们就可以枚举 xy 的因数，判断其是否符合题目所给条件。

Tips

• 在枚举的时候只需要枚举到 \sqrt{xy} 就行，对于每组合法数据，计算两次答案即可。
• 对于 x=y 的情况，在计算答案时会有重复，最后的答案是 ans-1。

AC code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int x, y, n, ans;
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
int lcm(int a, int b)
{
    return a / gcd(a, b) * b;
}
int main()
{
    ios::sync_with_stdio(0);
    cin >> x >> y;
    n = x * y; //用n来记录x与y的积
    for (int i = 1; i <= __builtin_sqrt(n); i++)
    /*
        __builtin_sqrt()与sqrt()功能相同，只不过速度更快,
        直接使用sqrt()也能通过本题
    */
        if (n % i == 0 && gcd(i, n / i) == x && lcm(i, n / i) == y)
            ans += 2;
    if (x == y) //去重
        ans--;
    cout << ans << '\n';
    return 0;
}

当然这段代码还可以优化，因为在乘积相等且最大公约数符合条件，最小公倍数也一定符合条件，所以我们可以省略第三个条件的判断，以下是简化版代码。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int x, y, n, ans;
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
int main()
{
    ios::sync_with_stdio(0);
    cin >> x >> y;
    n = x * y;
    for (int i = 1; i <= __builtin_sqrt(n); i++)
        if (n % i == 0 && gcd(i, n / i) == x)
            ans += 2;
    if (x == y)
        ans--;
    cout << ans << '\n';
    return 0;
}