luogu-P1029 最大公约数和最小公倍数问题

NOIP 2001 普及组真题，考察 最大公约数（GCD） 与 最小公倍数（LCM） 的数学性质。解题核心是利用 $\gcd(P, Q) \times \text{lcm}(P, Q) = P \times Q$ 的关系，将问题转化为枚举因数对并判断互质。适合GESP三级以上考生练习。题目难度⭐⭐，洛谷难度等级入门。

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

题目要求

题目描述

输入两个正整数 $x_0, y_0$，求出满足下列条件的 $P, Q$ 的个数：

1. $P,Q$ 是正整数。
2. 要求 $P, Q$ 以 $x_0$ 为最大公约数，以 $y_0$ 为最小公倍数。

试求：满足条件的所有可能的 $P, Q$ 的个数。

输入格式

一行两个正整数 $x_0, y_0$。

输出格式

一行一个数，表示求出满足条件的 $P, Q$ 的个数。

输入输出样例 #1

输入 #1

3 60

输出 #1

4

说明/提示

$P,Q$ 有 $4$ 种：

1. $3, 60$。
2. $15, 12$。
3. $12, 15$。
4. $60, 3$。

对于 $100\%$ 的数据，$2 \le x_0, y_0 \le {10}^5$。

【题目来源】

NOIP 2001 普及组第二题

题目分析

这道题考察的是最大公约数（GCD）与最小公倍数（LCM）的基本性质，以及因数枚举与互质判定的综合运用。

1. 关键数学性质

首先需要回顾一个基本公式：对于任意两个正整数 $P, Q$，有

题目要求 $\gcd(P, Q) = x_0$，$\text{lcm}(P, Q) = y_0$。由公式可得 $P \times Q = x_0 \times y_0$。

前提判断：$y_0$ 必须能被 $x_0$ 整除（因为 $\text{lcm}(P,Q)$ 一定是 $\gcd(P,Q)$ 的倍数）。如果 $y_0 \mod x_0 \neq 0$，则不存在满足条件的 $P, Q$，直接输出 $0$。

2. 变量替换与问题简化

令 $P = x_0 \times a$，$Q = x_0 \times b$。由于 $\gcd(P, Q) = x_0$，所以 $a, b$ 必须互质，即 $\gcd(a, b) = 1$。

同时由 $\text{lcm}(P, Q) = y_0$，可推出 $a \times b = y_0 / x_0$。记 $k = y_0 / x_0$。

这样问题转化为：求 $k$ 的因数对 $(a, b)$ 的个数，满足 $a \times b = k$ 且 $\gcd(a, b) = 1$。注意 $(a, b)$ 和 $(b, a)$ 算两种不同方案（因为对应不同的 $P, Q$）。

3. 枚举因数

从 $1$ 到 $\sqrt{k}$ 枚举 $a$，若 $k \mod a = 0$，则 $b = k / a$。然后判断 $\gcd(a, b)$ 是否等于 $1$：

• 如果 $a \neq b$（即 $a \neq \sqrt{k}$），则 $(a, b)$ 和 $(b, a)$ 是两种方案，计数加 $2$。
• 如果 $a = b$（即 $k$ 是完全平方数且 $a = \sqrt{k}$），则只有一种方案，计数加 $1$。但此时 $\gcd(a, a) = a$，只有 $a = 1$ 时才互质，即 $k = 1$ 的特殊情况。

复杂度分析：

• 时间复杂度：$O(\sqrt{y_0 / x_0} \times \log(y_0 / x_0))$，其中枚举因数为 $O(\sqrt{k})$，每次 GCD 计算为 $O(\log k)$。
• 空间复杂度：$O(1)$，只使用常数个变量。

示例代码

#include <algorithm>
#include <iostream>

// 辗转相除法求最大公约数
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int x0, y0;
    std::cin >> x0 >> y0;

    // 前提判断：最小公倍数必须是最大公约数的倍数
    if (y0 % x0 != 0) {
        std::cout << 0 << std::endl;
        return 0;
    }

    int k = y0 / x0; // 将问题转化为在 k 的因数中寻找互质对
    int count = 0;

    // 枚举 k 的因数，只需枚举到 sqrt(k)
    for (int a = 1; a * a <= k; a++) {
        if (k % a == 0) {
            int b = k / a;
            // 判断因数对 (a, b) 是否互质
            if (gcd(a, b) == 1) {
                if (a == b) {
                    count += 1; // a == b 时只有一种方案
                } else {
                    count += 2; // (a, b) 和 (b, a) 是两种不同方案
                }
            }
        }
    }

    std::cout << count << std::endl;

    return 0;
}

更直接的思路

上面的方法通过变量替换 $a = P / x_0$、$b = Q / x_0$ 将问题转化为"求 $k$ 的互质因数对"，虽然数学上更优雅，但理解起来多了一层抽象。

一种更直观的方法是：直接枚举 $P$，由 $P \times Q = x_0 \times y_0$ 算出 $Q$，然后验证 $\gcd(P, Q) = x_0$ 是否成立。

具体步骤：

1. 前提判断：$y_0 \mod x_0 \neq 0$ 则无解。
2. 枚举 $P$：$P$ 必须是 $x_0$ 的倍数（因为 $\gcd(P, Q) = x_0$ 意味着 $x_0 \mid P$），所以令 $P = x_0, 2x_0, 3x_0, \ldots$。
3. 计算 $Q$：由 $P \times Q = x_0 \times y_0$，得 $Q = x_0 \times y_0 / P$。需要 $P \mid (x_0 \times y_0)$ 且 $Q$ 为正整数。
4. 验证：检查 $\gcd(P, Q) = x_0$ 是否成立。
5. 优化枚举范围：只需枚举 $P \le Q$（即 $P^2 \le x_0 \times y_0$），找到一对后根据 $P$ 是否等于 $Q$ 计数 $1$ 或 $2$。

#include <algorithm>
#include <iostream>

// 辗转相除法求最大公约数
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int x0, y0;
    std::cin >> x0 >> y0;

    // 前提判断：最小公倍数必须是最大公约数的倍数
    if (y0 % x0 != 0) {
        std::cout << 0 << std::endl;
        return 0;
    }

    long long product = (long long)x0 * y0; // P * Q = x0 * y0
    int count = 0;

    // 直接枚举 P，P 必须是 x0 的倍数
    for (long long p = x0; p * p <= product; p += x0) {
        if (product % p == 0) {
            long long q = product / p;
            // 直接验证 gcd(P, Q) 是否等于 x0
            if (gcd(p, q) == x0) {
                if (p == q) {
                    count += 1;
                } else {
                    count += 2;
                }
            }
        }
    }

    std::cout << count << std::endl;

    return 0;
}

这种写法不需要做变量替换，思路更直白：枚举 → 计算 → 验证，更容易在考场上快速实现。

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号