NOIP 全国联赛真题
🎨 视觉封面【NOIP真题】2001 最大公约数和最小公倍数问题 luogu-P1029 | 适用于 GESP五级 / CSP-J 练习
最大公约数()与最小公倍数()是初等数论中最对称、最优雅的一对孪生概念。洛谷 P1029 [NOIP2001 普及组]《最大公约数和最小公倍数问题》给出两者的取值,要求反推满足条件的正整数数对 的组数。题目的突破口在于乘积恒等式 以及互质性转化 。从朴素的 枚举因数检验,到进一步利用质因数分解直接得出 计数,本题展示了数学恒等式如何将看似复杂的整除关系瞬间化为轻巧的计数逻辑。
luogu-P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题
🔗 洛谷原题传送门:luogu-P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题
题目描述
输入两个正整数 ,求出满足下列条件的 的个数:
-
是正整数。
-
要求 以 为最大公约数,以 为最小公倍数。
试求:满足条件的所有可能的 的个数。
输入格式
一行两个正整数 。
输出格式
一行一个数,表示求出满足条件的 的个数。
输入输出样例
输入 #1
3 60输出 #1
4说明/提示
有 种:
- 。
- 。
- 。
- 。
对于 的数据,。
【题目来源】
NOIP 2001 普及组第二题
题目深度剖析
1. 数学本质与代数恒等式推导
在初等数论中,任意两个正整数 和 的**最大公约数(GCD)与最小公倍数(LCM)**之间存在一个极其优美的基本代数恒等式:
根据题意,题目要求:
因此,任何合法的正整数对 ,它们的乘积必定是一个确定不变的常数:
同时,由最大公约数和最小公倍数的定义可知:
- 必须是 和 的公因数,即 且 ;
- 和 必须是 的因数,即 且 。
由此可以立即推导出解存在的必要先验条件:
若输入数据中 不能被 整除(即 ),则数学上绝不可能存在合法的正整数 ,此时满足条件的个数必然为 。
2. 代数置换与互质条件化简
由于 且 ,我们可以将 和 分离出公因子 ,设:
代入最大公约数定义式:
因为题设要求 ,所以必须严格满足:
再将 代入乘积恒等式:
记常数 ,整个题目被完整等价地规约简化为:
求满足乘积 且 的正整数有序对 的数量。
每一个合法的有序对 ,都一一对应着唯一的合法解 。
3. 因数枚举与对称性分析
要求满足 的数对,本质上就是寻找 的正因数对。
在自然数中,因数总是成对对称出现的:
- 若 是 的因数,则必有对应的因数 ;
- 我们不妨设 ,则必有 。
因此,我们只需要单层循环在 范围内递增枚举整数 :
- 若 ,说明找到了一组因数对 ,其中 ;
- 检验 与 是否互质:调用欧几里得算法计算 是否等于 ;
- 若 :
- 当 时(这只会在 为完全平方数且 即 时发生,因为 时 ),有序对 只有 种排列,计数累加 ;
- 当 时, 与 构成两组不同的有序对(对应不同的 ),计数累加 。
复杂度分析:
- 循环范围:,由于数据范围 ,则 ,,单层循环最多仅执行 次!
- 每次判定计算 :单次辗转相除法时间复杂度为 ;
- 总体时间复杂度:,总运算次数仅几千次,在现代评测机上耗时不足 ,极速 AC。
4. 数论深层拓展:算术基本定理与 快速计数法
从更深入的代数视角来看,本题还可以借助**算术基本定理(唯一分解定理)**直接求得答案:
将正整数 进行标准质因数分解:
由于要求 且 :
- 对于任意一个质因子 ,若 且 ,则必然导致 ,这与互质产生矛盾!
- 因此,对于每一个质因子幂次 ,必须作为一个不可分割的整体,要么全部归属于 (即 且 ),要么全部归属于 (即 且 )。
- 对于 个互不相同的质因子,每个质因子有且仅有 种分配选择,且各质因子的选择互相独立。
根据乘法原理,满足条件的有序对 的总数严格等于: 其中 为 的不同质因子的种类数。
例如样例中:
- ;
- ,不同的质因子有 和 两个(即 );
- 满足条件的方案数即为 种,与样例输出完全吻合!
两种方法在数学本质上殊途同归,因数枚举法适合 GESP 五级考场编码,质因子分解法则是更高阶的数论思维拓展。
5. 常见考场陷阱与避坑指南
-
整型溢出(“不开 long long 见祖宗”):
- 题目给定 ;
- 若选手直接枚举 并计算 ,在 32 位有符号整型
int下,乘积 最大可达 ,而 32 位整型上限仅为 ,将直接触发有符号整型乘法溢出! - 规范避坑:全程统一使用 64 位长整型
long long。
-
遗漏 的边界情况:
- 若输入的最小公倍数不能被最大公约数整除,必须特判输出 并直接退出,不可漏判。
-
有序对的对称性累加:
- 注意题目求的是所有可能的 对, 与 是两种不同的情况;
- 只有在 时才能只加 ;若 必须加 。
完整参考代码 (C++11)
/**
* Problem: luogu-P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题
* Algorithm: 初等数论 / 欧几里得算法 (GCD) 与 因数枚举
* Standard: C++11 (CCF GESP 官方大纲规范)
* Author: OneCoder
*/
#include <iostream>
using namespace std;
// 欧几里得算法(辗转相除法)求最大公约数
// gcd(a, b) = gcd(b, a % b),当 b 为 0 时递归基为 a
long long gcd(long long a, long long b) {
while (b != 0) {
long long r = a % b;
a = b;
b = r;
}
return a;
}
int main() {
// 读入给定的最大公约数 x0 和最小公倍数 y0
// 使用 64 位整型 long long 存储,避免中间乘积或数据运算溢出
long long x0, y0;
cin >> x0 >> y0;
// 前提合法性判定:
// 两个正整数的最小公倍数必须能被它们的最大公约数整除
// 若 y0 % x0 != 0,则数学上绝不可能存在符合条件的 P, Q,方案数直接为 0
if (y0 % x0 != 0) {
cout << 0 << endl;
return 0;
}
// 根据数论性质:
// 设 P = x0 * a, Q = x0 * b
// 则 gcd(P, Q) = x0 * gcd(a, b) = x0 => gcd(a, b) = 1 (即 a 与 b 互质)
// 又 lcm(P, Q) = x0 * a * b = y0 => a * b = y0 / x0
// 令 M = y0 / x0,问题转化为求乘积等于 M 且互质的正整数有序对 (a, b) 的组数
long long m = y0 / x0;
long long ans = 0;
// 根据因数成对分布的对称性,只需在 [1, sqrt(M)] 范围内枚举 a
// 循环条件写为 a * a <= m,变量为 long long 保证乘法不溢出
for (long long a = 1; a * a <= m; ++a) {
// 如果 a 能整除 m,则得到成对的因数 a 和 b
if (m % a == 0) {
long long b = m / a;
// 核心判定:a 与 b 必须互质,即最大公约数为 1
if (gcd(a, b) == 1) {
if (a == b) {
// 当 a == b 时(仅发生在 m 为 1 时),(a, b) 只有 1 种排列
ans += 1;
} else {
// 当 a != b 时,有序对 (a, b) 和 (b, a) 对应两组不同的 (P, Q)
// 方案数累加 2
ans += 2;
}
}
}
}
// 输出最终满足条件的所有可能的 P, Q 方案总数
cout << ans << endl;
return 0;
}所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI
欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。
猜你想读 · 相关文章推荐
【NOIP真题】2012 质因数分解 luogu-P1075 | 适用于 GESP五级 / CSP-J 练习
算术基本定理指出,任何大于 1 的自然数都能唯一分解为质数的乘积,而现代 RSA 等公钥密码学体系正是建立在大整数质因数分解的单向计算难度之上。洛谷 P1075 [NOIP2012 普及组]《质因数分解》以极度精炼的题目背景(已知 n 为两个不同质数的乘积,求较大质数)...
【NOIP真题】1997 luogu-P2241 统计方形(数据加强版) | GESP三、四级以上可练习
NOIP 1997 普及组第一题(洛谷 P2241 数据加强版),主要考察组合计数原理、循环枚举与数学规律推导。本题既可以通过双重循环枚举矩形的长宽直观求解,也可以通过组合数学与求和公式实现 O(min(n, m)) 乃至 O(1) 的高效求解。同时本题也是经典的“防溢...
【NOIP真题】2007 奖学金 luogu-P1093 | 适用于 GESP四级 / CSP-J 练习
在实际的评奖评优与考务系统中,如何按照多元维度公平、唯一地确定排名次序?洛谷 P1093 [NOIP2007 普及组]《奖学金》提供了一个标准的现实场景:根据三门课程总分、单科语文分以及学号先后来打破平局。这道题是信奥考查结构体建模(struct)与多关键字自定义排序规...
OneCoder
一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

