P1029【NOIP 2001 普及组】最大公约数和最小公倍数问题

1. 解题思路：暴力枚举

题目给出了两个正整数 x0 和 y0，要求统计有多少组正整数 (P, Q)，满足：

  • P 和 Q 的最大公约数为 x0。
  • P 和 Q 的最小公倍数为 y0。

需要注意，(P, Q) 和 (Q, P) 是两种不同的组合。例如 (12, 15) 和 (15, 12)，需要分别计数。

先考虑最直接的暴力枚举。

由于 x0 是 P 和 Q 的最大公约数，所以这两个数都必须是 x0 的倍数。

同时，y0 是它们的最小公倍数，因此 P 和 Q 都不可能大于 y0。

这样就确定了枚举范围：从 x0 开始，以 x0 为步长，分别枚举 P 和 Q。

对于每一组候选数字，只需要判断：

gcd⁡(P,Q)=x0\gcd(P,Q)=x_0

以及：

lcm⁡(P,Q)=y0\operatorname{lcm}(P,Q)=y_0

如果两个条件同时满足，就将答案加一。

Python 代码：

Python
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)
x0,y0=map(int,input().split())
count=0
for i in range(x0,y0+1,x0):
    for j in range(x0,y0+1,x0):
        if gcd(i,j)==x0 and i*j//gcd(i,j)==y0:
            count+=1
print(count)

C++ 代码：

C++
#include<iostream>
using namespace std;
#include<cmath>
#define int long long
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b)
{
    return abs(a * b) / gcd(a, b);
}
signed main()
{
    ios::sync_with_stdio;
    cin.tie();
    int x0, y0;
    cin >> x0 >> y0;
    int count = 0;
    for (int i = x0; i <= y0; i+=x0)
    {
        for (int j = x0; j <= y0; j+=x0)
        {
            if (gcd(i, j) == x0 && lcm(i, j) == y0)
            {
                count++;
            }
        }
    }
    cout << count;
}

这种方法理解起来比较简单，但实际提交时，我只通过了 8 个测试点，另外两个测试点因为超时没有通过。

问题主要出在双层循环上。

例如，当 x0 = 2、y0 = 100000 时，每层循环都需要枚举 50000 个数。

两层循环组合起来，一共需要进行：

50000×50000=250000000050000\times50000=2500000000

也就是 25 亿次判断。

即使每次判断的计算量不大，这样的枚举次数也很难在规定时间内完成。

那么，有没有办法只枚举其中一个数，而不用把所有 (P, Q) 的组合都检查一遍呢？

2. 利用最大公约数与最小公倍数的关系优化

回顾一下最大公约数和最小公倍数之间的关系：

lcm⁡(a,b)=a×bgcd⁡(a,b)\operatorname{lcm}(a,b)=\frac{a\times b}{\gcd(a,b)}

将公式变形，可以得到：

a×b=gcd⁡(a,b)×lcm⁡(a,b)a\times b=\gcd(a,b)\times\operatorname{lcm}(a,b)

对于这道题，P 和 Q 的最大公约数、最小公倍数都是已知的，因此：

P×Q=x0×y0P\times Q=x_0\times y_0

这就意味着，只要确定了 P，就能直接计算出对应的 Q。

Q=x0×y0PQ=\frac{x_0\times y_0}{P}

例如，题目给出 x0 = 3、y0 = 60。

那么：

P×Q=3×60=180P\times Q=3\times60=180

假设枚举到 P = 12，就可以得到：

Q=18012=15Q=\frac{180}{12}=15

再检查这两个数：

gcd⁡(12,15)=3\gcd(12,15)=3 lcm⁡(12,15)=60\operatorname{lcm}(12,15)=60

两个条件都满足，因此 (12, 15) 是一组合法答案。

这样一来，我们就不需要使用两层循环分别枚举 P 和 Q，而是可以按照下面的步骤进行：

  1. 从 x0 开始，以 x0 为步长枚举 P。
  2. 根据 Q = x0 × y0 / P 计算另一个数。
  3. 检查 Q 是否为正整数，以及这两个数的最大公约数、最小公倍数是否满足要求。
  4. 满足条件就将答案加一。

原本需要枚举的两个变量，现在只剩下一个，循环次数大幅减少。

3. 优化后的代码实现

C++ 代码：

C++
#include<iostream>
using namespace std;
#include<cmath>
#define int long long
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b)
{
    return abs(a * b) / gcd(a, b);
}
signed main()
{
    ios::sync_with_stdio;
    cin.tie();
    int x0, y0;
    cin >> x0 >> y0;
    int count = 0;
    for (int P = x0; P <= y0; P += x0)
    {
        int Q = (x0 * y0) / P;
        if (gcd(Q, P) == x0 && lcm(Q, P) == y0)
        {
            // cout << P <<" "<< Q <<" "<<gcd(Q,P) << endl;
            count++;
        }
    }
    cout << count;
}

Python 代码：

Python
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)
def lcm(a,b):
    return a*b//gcd(a,b)
x0,y0=map(int,input().split())
count=0
flag=0
for P in range(x0,y0+1,x0):
    Q=x0*y0/P
    if gcd(P,Q)==x0 and lcm(P,Q)==y0:
        count+=1
print(count)

这里还有一个需要注意的地方：通过公式算出的 Q，不一定是整数。

例如，仍然使用 x0 = 3、y0 = 60，如果枚举到 P = 9，那么：

Q=1809=20Q=\frac{180}{9}=20

虽然 Q 是整数，但 9 和 20 的最大公约数为 1，不满足题目要求。

而如果枚举到 P = 21：

Q=18021Q=\frac{180}{21}

结果不是整数，自然也不能作为合法答案。

因此，公式只是帮助我们快速确定另一个数，并不意味着得到的数对一定符合要求。

我们仍然需要检查候选数对是否合法。

4. 复杂度分析

假设每层循环需要枚举的候选数量为：

M=⌊y0x0⌋M=\left\lfloor\frac{y_0}{x_0}\right\rfloor

暴力枚举需要使用两层循环，大约检查 M2M^2 组数对。

优化后只需要枚举 P，每次直接计算 Q，因此只需要检查大约 MM 组候选。

由于每次检查还需要计算最大公约数，考虑辗转相除法的时间开销后：

解法时间复杂度
双层暴力枚举O(M2log⁡y0)O(M^2\log y_0)
单层枚举优化O(Mlog⁡y0)O(M\log y_0)

虽然仍然需要逐个检查候选数对，但相比原来的双重枚举，计算量已经减少了很多。

这道题的关键在于利用已知的最大公约数和最小公倍数，推导出两个未知数之间的乘积关系。

找到这个关系后，就能由一个数直接确定另一个数，从而把双层枚举优化成单层枚举。

谢谢你读到这里。 ✧

聊两句

评论审核后显示

有疑问、补充，或者想交流一下，都可以写在这里。

评论区将在滚动到这里时加载。