【GESP/CSP练习】GESP五级 / CSP-J 题解：luogu-P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题

NOIP 2001 普及组第二题，洛谷 P1029。本题是算法竞赛与等级考试中极为经典的初等数论、欧几里得算法与因数枚举代表作，标准收录于 CCF GESP 五级考纲（初等数论：最大公约数 $\gcd$、最小公倍数 $\operatorname{lcm}$、质因数分解与欧几里得算法考点）以及 CSP-J 普及组数论必做题单。题目核心考察如何利用数论恒等式 $\gcd(P, Q) \times \operatorname{lcm}(P, Q) = P \times Q$ 进行代数变形，将原问题转化为求商值 $M$ 的互质因数对 $(a, b)$，并依托因数成对对称分布规律在 $\mathcal{O}(\sqrt{M} \log M)$ 的高效率下快速完成求解。题目难度⭐⭐☆☆☆，洛谷难度等级评定为普及-。

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

🔗 洛谷原题传送门：luogu-P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题

题目描述

输入两个正整数 $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

13 60

输出 #1

14

说明/提示

$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 普及组第二题

题目深度剖析

1. 数学本质与代数恒等式推导

在初等数论中，任意两个正整数 $P$ 和 $Q$ 的**最大公约数（GCD）与最小公倍数（LCM）**之间存在一个极其优美的基本代数恒等式：

$P \times Q = \gcd(P, Q) \times \operatorname{lcm}(P, Q)$

根据题意，题目要求：

• $\gcd(P, Q) = x_0$
• $\operatorname{lcm}(P, Q) = y_0$

因此，任何合法的正整数对 $(P, Q)$，它们的乘积必定是一个确定不变的常数： $P \times Q = x_0 \times y_0$

同时，由最大公约数和最小公倍数的定义可知：

• $x_0$ 必须是 $P$ 和 $Q$ 的公因数，即 $x_0 \mid P$ 且 $x_0 \mid Q$；
• $P$ 和 $Q$ 必须是 $y_0$ 的因数，即 $P \mid y_0$ 且 $Q \mid y_0$。

由此可以立即推导出解存在的必要先验条件： $\operatorname{lcm}(P, Q) \text{ 必须能被 } \gcd(P, Q) \text{ 整除，即 } y_0 \bmod x_0 = 0$

若输入数据中 $y_0$ 不能被 $x_0$ 整除（即 $y_0 \bmod x_0 \ne 0$），则数学上绝不可能存在合法的正整数 $P, Q$，此时满足条件的个数必然为 $0$。

2. 代数置换与互质条件化简

由于 $x_0 \mid P$ 且 $x_0 \mid Q$，我们可以将 $P$ 和 $Q$ 分离出公因子 $x_0$，设： $P = x_0 \times a, \quad Q = x_0 \times b \quad (a, b \in \mathbb{Z}^+)$

代入最大公约数定义式： $\gcd(P, Q) = \gcd(x_0 \cdot a, x_0 \cdot b) = x_0 \cdot \gcd(a, b)$

因为题设要求 $\gcd(P, Q) = x_0$，所以必须严格满足： $\gcd(a, b) = 1 \quad (\text{即 } a \text{ 与 } b \text{ 互质})$

再将 $P, Q$ 代入乘积恒等式： $(x_0 \cdot a) \times (x_0 \cdot b) = x_0 \times y_0 \implies a \times b = \frac{y_0}{x_0}$

记常数 $M = \frac{y_0}{x_0}$，整个题目被完整等价地规约简化为：

求满足乘积 $a \times b = M$ 且 $\gcd(a, b) = 1$ 的正整数有序对 $(a, b)$ 的数量。

每一个合法的有序对 $(a, b)$，都一一对应着唯一的合法解 $(P, Q) = (x_0 \cdot a, x_0 \cdot b)$。

3. 因数枚举与对称性分析

要求满足 $a \times b = M$ 的数对，本质上就是寻找 $M$ 的正因数对。

在自然数中，因数总是成对对称出现的：

• 若 $a$ 是 $M$ 的因数，则必有对应的因数 $b = \frac{M}{a}$；
• 我们不妨设 $a \le b$，则必有 $a \le \sqrt{M}$。

因此，我们只需要单层循环在 $[1, \lfloor\sqrt{M}\rfloor]$ 范围内递增枚举整数 $a$：

1. 若 $M \bmod a = 0$，说明找到了一组因数对 $(a, b)$，其中 $b = \frac{M}{a}$；
2. 检验 $a$ 与 $b$ 是否互质：调用欧几里得算法计算 $\gcd(a, b)$ 是否等于 $1$；
3. 若 $\gcd(a, b) = 1$：
   • 当 $a = b$ 时（这只会在 $M$ 为完全平方数且 $a = 1, b = 1$ 即 $M = 1$ 时发生，因为 $a \ne 1$ 时 $\gcd(a, a) = a \ne 1$），有序对 $(a, b)$ 只有 $1$ 种排列，计数累加 $1$；
   • 当 $a \ne b$ 时，$(a, b)$ 与 $(b, a)$ 构成两组不同的有序对（对应不同的 $P, Q$），计数累加 $2$。

复杂度分析：

• 循环范围：$a \in [1, \sqrt{M}]$，由于数据范围 $y_0 \le 10^5$，则 $M \le 10^5$，$\sqrt{M} \le \sqrt{10^5} \approx 316.2$，单层循环最多仅执行 $316$ 次！
• 每次判定计算 $\gcd(a, b)$：单次辗转相除法时间复杂度为 $\mathcal{O}(\log M)$；
• 总体时间复杂度：$\mathcal{O}(\sqrt{M} \log M)$，总运算次数仅几千次，在现代评测机上耗时不足 $1\text{ms}$，极速 AC。

4. 数论深层拓展：算术基本定理与 $2^m$ 快速计数法

从更深入的代数视角来看，本题还可以借助**算术基本定理（唯一分解定理）**直接求得答案：

将正整数 $M = \frac{y_0}{x_0}$ 进行标准质因数分解： $M = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m} \quad (p_i \text{ 为互不相同的质数}, k_i \ge 1)$

由于要求 $a \times b = M$ 且 $\gcd(a, b) = 1$：

• 对于任意一个质因子 $p_i$，若 $p_i \mid a$ 且 $p_i \mid b$，则必然导致 $\gcd(a, b) \ge p_i > 1$，这与互质产生矛盾！
• 因此，对于每一个质因子幂次 $p_i^{k_i}$，必须作为一个不可分割的整体，要么全部归属于 $a$（即 $p_i^{k_i} \mid a$ 且 $p_i \nmid b$），要么全部归属于 $b$（即 $p_i^{k_i} \mid b$ 且 $p_i \nmid a$）。
• 对于 $m$ 个互不相同的质因子，每个质因子有且仅有 $2$ 种分配选择，且各质因子的选择互相独立。

根据乘法原理，满足条件的有序对 $(a, b)$ 的总数严格等于： $\text{Ans} = 2^m$ 其中 $m$ 为 $M$ 的不同质因子的种类数。

例如样例中：

• $x_0 = 3, y_0 = 60 \implies M = \frac{60}{3} = 20$；
• $20 = 2^2 \times 5^1$，不同的质因子有 $2$ 和 $5$ 两个（即 $m = 2$）；
• 满足条件的方案数即为 $2^2 = 4$ 种，与样例输出完全吻合！

两种方法在数学本质上殊途同归，因数枚举法适合 GESP 五级考场编码，质因子分解法则是更高阶的数论思维拓展。

5. 常见考场陷阱与避坑指南

1. 整型溢出（“不开 long long 见祖宗”）：

   • 题目给定 $x_0, y_0 \le 10^5$；
   • 若选手直接枚举 $P$ 并计算 $Q = \frac{x_0 \times y_0}{P}$，在 32 位有符号整型 int 下，乘积 $x_0 \times y_0$ 最大可达 $10^5 \times 10^5 = 10^{10}$，而 32 位整型上限仅为 $2.14 \times 10^9$，将直接触发有符号整型乘法溢出！
   • 规范避坑：全程统一使用 64 位长整型 long long。

2. 遗漏 $y_0 \bmod x_0 \ne 0$ 的边界情况：

   • 若输入的最小公倍数不能被最大公约数整除，必须特判输出 $0$ 并直接退出，不可漏判。

3. 有序对的对称性累加：

   • 注意题目求的是所有可能的 $P, Q$ 对，$(3, 60)$ 与 $(60, 3)$ 是两种不同的情况；
   • 只有在 $a = b$ 时才能只加 $1$；若 $a \ne b$ 必须加 $2$。

完整参考代码 (C++11)

1/**
2 * Problem: luogu-P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题
3 * Algorithm: 初等数论 / 欧几里得算法 (GCD) 与 因数枚举
4 * Standard: C++11 (CCF GESP 官方大纲规范)
5 * Author: OneCoder
6 */
7
8#include <iostream>
9
10using namespace std;
11
12// 欧几里得算法（辗转相除法）求最大公约数
13// gcd(a, b) = gcd(b, a % b)，当 b 为 0 时递归基为 a
14long long gcd(long long a, long long b) {
15    while (b != 0) {
16        long long r = a % b;
17        a = b;
18        b = r;
19    }
20    return a;
21}
22
23int main() {
24    // 读入给定的最大公约数 x0 和最小公倍数 y0
25    // 使用 64 位整型 long long 存储，避免中间乘积或数据运算溢出
26    long long x0, y0;
27    cin >> x0 >> y0;
28
29    // 前提合法性判定：
30    // 两个正整数的最小公倍数必须能被它们的最大公约数整除
31    // 若 y0 % x0 != 0，则数学上绝不可能存在符合条件的 P, Q，方案数直接为 0
32    if (y0 % x0 != 0) {
33        cout << 0 << endl;
34        return 0;
35    }
36
37    // 根据数论性质：
38    // 设 P = x0 * a, Q = x0 * b
39    // 则 gcd(P, Q) = x0 * gcd(a, b) = x0  =>  gcd(a, b) = 1 (即 a 与 b 互质)
40    // 又 lcm(P, Q) = x0 * a * b = y0      =>  a * b = y0 / x0
41    // 令 M = y0 / x0，问题转化为求乘积等于 M 且互质的正整数有序对 (a, b) 的组数
42    long long m = y0 / x0;
43    long long ans = 0;
44
45    // 根据因数成对分布的对称性，只需在 [1, sqrt(M)] 范围内枚举 a
46    // 循环条件写为 a * a <= m，变量为 long long 保证乘法不溢出
47    for (long long a = 1; a * a <= m; ++a) {
48        // 如果 a 能整除 m，则得到成对的因数 a 和 b
49        if (m % a == 0) {
50            long long b = m / a;
51
52            // 核心判定：a 与 b 必须互质，即最大公约数为 1
53            if (gcd(a, b) == 1) {
54                if (a == b) {
55                    // 当 a == b 时（仅发生在 m 为 1 时），(a, b) 只有 1 种排列
56                    ans += 1;
57                } else {
58                    // 当 a != b 时，有序对 (a, b) 和 (b, a) 对应两组不同的 (P, Q)
59                    // 方案数累加 2
60                    ans += 2;
61                }
62            }
63        }
64    }
65
66    // 输出最终满足条件的所有可能的 P, Q 方案总数
67    cout << ans << endl;
68
69    return 0;
70}