【NOIP】2001真题解析 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$ 的个数：
- $P,Q$ 是正整数。
- 要求 $P, Q$ 以 $x_0$ 为最大公约数，以 $y_0$ 为最小公倍数。
试求：满足条件的所有可能的 $P, Q$ 的个数。
输入格式
一行两个正整数 $x_0, y_0$。
输出格式
一行一个数，表示求出满足条件的 $P, Q$ 的个数。
输入输出样例 #1
输入 #1
1
3 60
输出 #1
1
4
说明/提示
$P,Q$ 有 $4$ 种：
- $3, 60$。
- $15, 12$。
- $12, 15$。
- $60, 3$。
对于 $100\%$ 的数据，$2 \le x_0, y_0 \le {10}^5$。
【题目来源】
NOIP 2001 普及组第二题
题目分析
这道题考察的是最大公约数（GCD）与最小公倍数（LCM）的基本性质，以及因数枚举与互质判定的综合运用。
1. 关键数学性质
首先需要回顾一个基本公式：对于任意两个正整数 $P, Q$，有
\[\gcd(P, Q) \times \text{lcm}(P, Q) = P \times 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)$，只使用常数个变量。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#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$ 是否成立。
具体步骤：
- 前提判断：$y_0 \mod x_0 \neq 0$ 则无解。
- 枚举 $P$：$P$ 必须是 $x_0$ 的倍数（因为 $\gcd(P, Q) = x_0$ 意味着 $x_0 \mid P$），所以令 $P = x_0, 2x_0, 3x_0, \ldots$。
- 计算 $Q$：由 $P \times Q = x_0 \times y_0$，得 $Q = x_0 \times y_0 / P$。需要 $P \mid (x_0 \times y_0)$ 且 $Q$ 为正整数。
- 验证：检查 $\gcd(P, Q) = x_0$ 是否成立。
- 优化枚举范围：只需枚举 $P \le Q$（即 $P^2 \le x_0 \times y_0$），找到一对后根据 $P$ 是否等于 $Q$ 计数 $1$ 或 $2$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#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;
}
这种写法不需要做变量替换，思路更直白：枚举 → 计算 → 验证，更容易在考场上快速实现。
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
"luogu-"系列题目可在洛谷题库进行在线评测。
"bcqm-"系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
