专栏文章

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

SS_Y_B_S
P1029题解参与者 3已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@miq9v968
此快照首次捕获于
2025/12/04 01:19
3 个月前
此快照最后确认于
2025/12/04 01:19
3 个月前
查看原文

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

前置芝士

最大公约数 gcd⁡\gcd，这里提供一种参考写法（当然你也可以用内置函数__gcd()）：
CPP
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
以及最小公倍数 lcm⁡\operatorname{lcm}（当然本题也可以不求 lcm⁡\operatorname{lcm}，后面会说到）：
CPP
int lcm(int a, int b)
{
    return a / gcd(a, b) * b;
    //这里先除再乘是好习惯，避免溢出
}

思路

本题我们可以利用关于最大公约数与最小公倍数的小小的性质，即：
gcd⁡(a,b)×lcm⁡(a,b)=a×b\gcd(a,b)\times \operatorname{lcm}(a,b)=a\times b
所以，对于任意一组合法的 p,qp,q，一定有 xy=pqxy=pq。
然后我们就可以枚举 xyxy 的因数，判断其是否符合题目所给条件。

Tips

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

AC code

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

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...