【NOIP真题】2001 最大公约数和最小公倍数问题 luogu-P1029 | 适用于 GESP五级 / CSP-J 练习

最大公约数（）与最小公倍数（）是初等数论中最对称、最优雅的一对孪生概念。洛谷 P1029 [NOIP2001 普及组]《最大公约数和最小公倍数问题》给出两者的取值，要求反推满足条件的正整数数对  的组数。题目的突破口在于乘积恒等式  以及互质性转化 。从朴素的  枚举因数检验，到进一步利用质因数分解直接得出  计数，本题展示了数学恒等式如何将看似复杂的整除关系瞬间化为轻巧的计数逻辑。

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

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

🔹 题目描述

输入两个正整数 ，求出满足下列条件的  的个数：

1.  是正整数。

2. 要求  以  为最大公约数，以  为最小公倍数。

试求：满足条件的所有可能的  的个数。

🔹 输入格式

一行两个正整数 。

🔹 输出格式

一行一个数，表示求出满足条件的  的个数。

🔹 输入输出样例

输入 #1

输出 #1

🔹 说明/提示

 有  种：

1. 。
2. 。
3. 。
4. 。

对于  的数据，。

【题目来源】

NOIP 2001 普及组第二题

🔹 题目深度剖析

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

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

根据题意，题目要求：

因此，任何合法的正整数对 ，它们的乘积必定是一个确定不变的常数：

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

•  必须是  和  的公因数，即  且 ；
•  和  必须是  的因数，即  且 。

由此可以立即推导出解存在的必要先验条件：

若输入数据中  不能被  整除（即 ），则数学上绝不可能存在合法的正整数 ，此时满足条件的个数必然为 。

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

由于  且 ，我们可以将  和  分离出公因子 ，设：

代入最大公约数定义式：

因为题设要求 ，所以必须严格满足：

再将  代入乘积恒等式：

记常数 ，整个题目被完整等价地规约简化为：

求满足乘积  且  的正整数有序对  的数量。

每一个合法的有序对 ，都一一对应着唯一的合法解 。

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

要求满足  的数对，本质上就是寻找  的正因数对。

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

• 若  是  的因数，则必有对应的因数 ；
• 我们不妨设 ，则必有 。

因此，我们只需要单层循环在  范围内递增枚举整数 ：

1. 若 ，说明找到了一组因数对 ，其中 ；
2. 检验  与  是否互质：调用欧几里得算法计算  是否等于 ；
3. 若 ： 
• 当  时（这只会在  为完全平方数且  即  时发生，因为  时 ），有序对  只有  种排列，计数累加 ；
• 当  时， 与  构成两组不同的有序对（对应不同的 ），计数累加 。

复杂度分析：

• 循环范围：，由于数据范围 ，则 ，，单层循环最多仅执行  次！
• 每次判定计算 ：单次辗转相除法时间复杂度为 ；
• 总体时间复杂度：，总运算次数仅几千次，在现代评测机上耗时不足 ，极速 AC。

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

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

将正整数  进行标准质因数分解：

由于要求  且 ：

• 对于任意一个质因子 ，若  且 ，则必然导致 ，这与互质产生矛盾！
• 因此，对于每一个质因子幂次 ，必须作为一个不可分割的整体，要么全部归属于 （即  且 ），要么全部归属于 （即  且 ）。
• 对于  个互不相同的质因子，每个质因子有且仅有  种分配选择，且各质因子的选择互相独立。

根据乘法原理，满足条件的有序对  的总数严格等于：

例如样例中：

• ；
• ，不同的质因子有  和  两个（即 ）；
• 满足条件的方案数即为  种，与样例输出完全吻合！

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

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

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

• 题目给定 ；
• 若选手直接枚举  并计算 ，在 32 位有符号整型 int 下，乘积  最大可达 ，而 32 位整型上限仅为 ，将直接触发有符号整型乘法溢出！
• 规范避坑
  ：全程统一使用 64 位长整型 long long。

2. 遗漏  的边界情况：

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

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

• 注意题目求的是所有可能的  对， 与  是两种不同的情况；
• 只有在  时才能只加 ；若  必须加 。

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