洛谷-P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题

题目链接:P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题

题目给出 x0 和 y0，要求统计有多少组正整数 P、Q，满足最大公约数为 x0、最小公倍数为 y0。

先考虑穷举。P、Q 都能被 x0 整除，又都不大于最小公倍数 y0，因此可以从 x0 开始，以 x0 为步长分别枚举两个数，再检查是否满足条件。

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++ 代码如下：

#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 次，两层循环组合起来就是 25 亿次判断。

可以利用最大公约数和最小公倍数的关系：因为 $lcm(x,y)=\frac{x\times y}{gcd(x,y)}$ ，所以 $gcd(x,y)\times lcm(x,y)=x\times y$ 。两者的乘积已知，只要枚举其中一个数，就能算出另一个数，再检查它们是否满足条件。这样就把双层循环缩减成了单层循环。

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 代码如下：

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)

求出 P、Q 后仍要验证： $\frac{(x0 \times y0) }{P}$ 不一定是整数，而题目要求 P、Q 都是正整数；整数候选还需要满足指定的 gcd 和 lcm。题目数据上限为 $10^5$ ，改成单层枚举后再逐项检查，开销比双重枚举小得多。