聊一道洛谷上的经典普及组题——P1029题名《最大公约数和最小公倍数问题》来自 NOIP2001 普及组。题目本身很短读一遍就能懂什么意思但真要动手写很多人第一次都会卡在怎么枚举、怎么计数上。我见过不少同学对着样例3 60输出4一头雾水想不明白(12,15)和(15,12)为什么算两组。如果你也有这个疑惑这篇题解就是为你准备的。先说结论这道题值得认真做三遍。第一遍用暴力过样例第二遍用约数枚举优化第三遍用质因数分解把它变成一道组合计数题。三遍下来你对最大公约数、最小公倍数、互质这三个概念的理解基本就超过一大半刷题人了。整篇文章我会从题目拆解、数学推导、三种代码实现、常见坑位、扩展套路五个部分展开新手可以直接照着代码抄有基础的人也可以重点看第二章的推导和第五章的延伸。1. 题目拆解P1029 到底在考察什么1.1 题干回顾与样例分析题目要求很直白输入两个正整数x0, y0求出所有满足以下条件的正整数对(P, Q)的个数P, Q的最大公约数是x0P, Q的最小公倍数是y0样例给的是x0 3, y0 60输出4。看到这个4不妨手动枚举一下符合条件的数对(3, 60)gcd(3,60)3lcm(3,60)60成立(12, 15)gcd(12,15)3lcm(12,15)60成立(15, 12)同样成立(60, 3)同样成立所以答案是4。注意这里(12,15)和(15,12)被当成了两个不同的方案也就是说题目统计的是有序数对。这一点很容易被忽略很多新手按照“两个数一组”去计数得出2交上去就 WA 了。后面第三章的代码里我会专门说明计数时为什么要加2。1.2 核心考点拆解这道题表面上是“给定最大公约数和最小公倍数反求数对”实际上考察了四个基础能力最大公约数与最小公倍数的关系它们不是独立的中间隔着一条核心公式gcd * lcm P * Q能不能想到这条公式决定了你是暴力枚举还是优雅计数。互质判断把P, Q同时除以x0之后剩下的两个数必须互质。这个结论是整套解法的灵魂。枚举上界的确定很多人第一反应是两层循环枚举P和Q但P和Q的范围可以到十万人次双层循环直接超时。能不能把枚举范围压缩到√n甚至完全不用枚举是区分“暴力选手”和“数学选手”的分水岭。特殊数据的处理比如x0不能整除y0时答案直接是0再比如x0 y0时答案只有1。这些边界情况不做特判很容易写出“样例能过、提交全错”的代码。说白了这题不考任何高深算法考的是你对数论基础概念的理解是否到位以及能不能把理解转化成代码。想通这一层你后面再看任何 gcd/lcm 相关的题目都会顺手很多。2. 数学原理三个关键公式帮你建立解题直觉2.1 最大公约数与最小公倍数的乘积关系第一个要刻进脑子里的公式是gcd(P, Q) * lcm(P, Q) P * Q这个公式在竞赛数论里几乎天天见。简单证明一下令g gcd(P, Q)那么可以写成P g * aQ g * b其中a和b互质。此时最小公倍数就是g * a * b。于是gcd(P, Q) * lcm(P, Q) g * (g * a * b) g² * a * b (g * a) * (g * b) P * Q这个结论成立的关键在于a和b互质。如果a和b还有公共因子那g就不是最大公约数公式也就不成立了。有了这条公式这道题就多了一个思路既然P * Q x0 * y0那么只要枚举P就能直接算出Q x0 * y0 / P不用再两层循环了。但要注意这只是第一步优化真正的数学解法比这还要优雅。2.2 变量替换把问题改成“互质数对乘积固定”接下来做一步关键替换。因为条件里说了gcd(P, Q) x0所以P和Q必然是x0的倍数。于是可以设P x0 * aQ x0 * b那么gcd(P, Q) x0 * gcd(a, b)这个结论可以验证提取公因子后互质的部分不会影响 gcd。题目要求gcd(P, Q) x0所以必然有gcd(a, b) 1也就是a和b互质。再看lcm(P, Q)。因为P和Q中都含有一个共同的x0且a、b互质所以lcm(P, Q) x0 * a * b题目要求lcm(P, Q) y0于是得到x0 * a * b y0即a * b y0 / x0这一步做完题目就完全变了一个样子求有多少对互质的正整数(a, b)使得它们的乘积等于y0 / x0。这个转换的好处是巨大的。原本P和Q是两个独立的未知数现在它们的关系被压缩成了“乘积固定”这一条原本要判断 gcd 和 lcm 两个条件现在只要判断互质一个条件。后面所有解法本质都是在处理“互质数对乘积固定”这个问题。2.3 质因数分配把枚举题变成计数题如果只要求“乘积固定”那方法就是枚举约数但如果还要求“互质”就可以进一步用质因数分解来思考。假设n y0 / x0把n做质因数分解n p1^e1 * p2^e2 * ... * pk^ek其中p1, p2, ..., pk是互不相同的质因子。现在要找互质的a, b满足a * b n。关键来了因为a和b互质同一个质因子不能同时出现在a和b里否则它们就有公共因子了。所以对于每个质因子pi^ei它的全部幂次只能整体分给a或者整体分给b绝不能拆分。每个质因子有 2 种归属一共有k个不同质因子所以合法的(a, b)有序对数量就是2^k拿样例验证x03, y060n202²×5不同质因子个数k2答案就是2²4。和输出完全一致。这个推导相当漂亮它把一道“找到所有数对再逐个验证”的题目压缩成了一行1 k的计算。做竞赛题多了你会发现很多“枚举题”背后都藏着类似的组合计数逻辑找到它代码量能少一个量级。3. 三种解法的完整实现3.1 解法一质因数分解 组合计数最推荐既然第二章已经推出了2^k这个结论代码实现就非常直接先判断y0能不能整除x0能的话对n y0 / x0做质因数分解统计不同质因子个数输出1 k。#include bits/stdc.h using namespace std; int main() { int x0, y0; cin x0 y0; // 关键特判gcd 必须整除 lcm否则无解 if (y0 % x0 ! 0) { cout 0 endl; return 0; } int n y0 / x0; int cnt 0; // 统计不同质因子的个数 // 质因数分解注意循环条件用 i n / i 防止溢出 for (int i 2; i n / i; i) { if (n % i 0) { cnt; // 遇到一个新的质因子 while (n % i 0) { n / i; // 把这个质因子全部除干净 } } } // 如果 n 还剩下一个大于1的数说明它是一个大质因子 if (n 1) cnt; cout (1 cnt) endl; return 0; }逐段解释一下先做y0 % x0的特判。这一步不是锦上添花而是必需。如果x0不能整除y0后面n y0 / x0会丢掉余数算出来的答案全是错的。数学上gcd(P,Q)必须整除lcm(P,Q)所以这个特判的语义是“无解直接输出0”。质因数分解用i n / i而不是i * i n原因是i * i在i很大的时候可能溢出int写成除法更安全。这在竞赛里是一个非常常见的细节坑。1 cnt中的cnt最大也就 6 左右因为n 100000而2×3×5×7×11×13 30030再乘一个 17 就超过十万了所以完全不用担心移位溢出。这个解法的复杂度是O(√n)n最大十万的量级也只有几百次运算跑起来是毫秒级。代码短、思路清晰是我最推荐的一种写法。3.2 解法二约数对枚举 gcd 判断最容易理解如果你觉得“质因子分配”的跳跃有点大没问题还有一条更直白的路直接枚举n的所有约数对(i, j)判断i和j是否互质。互质就计数不互质就跳过。#include bits/stdc.h using namespace std; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int main() { int x0, y0; cin x0 y0; if (y0 % x0 ! 0) { cout 0 endl; return 0; } int n y0 / x0; int ans 0; // 只枚举到 sqrt(n)另一半约数可以对称得到 for (int i 1; i n / i; i) { if (n % i 0) { int j n / i; if (gcd(i, j) 1) { if (i j) { ans 1; // i j 只有 ij1 这一种情况 } else { ans 2; // (i,j) 和 (j,i) 都合法 } } } } cout ans endl; return 0; }这个做法背后的逻辑是a * b n的每一对互质约数都对应一组(P, Q)。因为P x0 * aQ x0 * b所以枚举i从 1 到√nj n / i天然覆盖了所有约数对。为什么i ! j时加 2因为题目算的是有序数对a4, b5对应(P,Q)(12,15)而a5, b4对应(15,12)它们是两个不同的答案。只有i j 1这种特殊情况交换后还是同一对所以只加 1。复杂度是O(√n log n)多出来的log n来自每次 gcd 的辗转相除。实际运行起来依然飞快而且比质因数分解法更容易让新手理解“为什么互质就能计数”。如果你是在给别人讲题我建议先用这个解法打底再引出 2^k 的组合计数。3.3 解法三暴力枚举 乘积关系新手的保底方案第三种方法最朴素但也不能说没用——当你实在推不出来的时候至少还有一条路能 AC。思路就是用P * Q x0 * y0这个公式枚举P为x0的倍数算出Q x0 * y0 / P然后检查gcd(P, Q)是否等于x0且lcm(P, Q)是否等于y0。#include bits/stdc.h using namespace std; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } long long lcm(int a, int b) { return 1LL * a / gcd(a, b) * b; // 先除后乘避免溢出 } int main() { int x0, y0; cin x0 y0; int ans 0; // P 必须是 x0 的倍数且 P 的范围在 x0 到 y0 之间 for (int p x0; p y0; p x0) { if ((1LL * x0 * y0) % p ! 0) continue; // 必须整除否则 Q 不是整数 int q 1LL * x0 * y0 / p; if (gcd(p, q) x0 lcm(p, q) y0) { ans; } } cout ans endl; return 0; }这个解法的时间复杂度是O(y0 / x0 * log y0)。最坏情况是x02, y0100000时循环约五万次每次做两次 gcd总操作量在百万级别洛谷评测机完全跑得动。但这里有两个致命细节必须注意1LL * x0 * y0一定要用long long。x0 * y0最大是10^10直接乘会爆int。q也要用int接住因为x0 * y0 / p的值实际上不会超过y0的范围但中间过程的乘法必须先提升到long long。暴力的好处是逻辑简单、不容易写错适合在考场上一筹莫展时保底用。坏处是它没有利用互质条件代码里同时判断了 gcd 和 lcm逻辑上有一点冗余而且当数据范围放大到百万甚至千万级别时它就跑不动了。所以它只能算“保底方案”不是“最优方案”。3.4 三种方法对比与语言迁移三种方法放在一起看差异一目了然解法核心思想时间复杂度代码量适合场景质因数分解法互质等价于质因子整体分配O(√n)最短竞赛正解推荐掌握约数对枚举法枚举约数对 gcd 判断O(√n log n)中等最易理解适合讲题暴力枚举法PQx0y0 逐个验证O((y0/x0) log y0)中等保底方案新手可写如果用的是 Python算法思路完全一样只是语法不同。约数对枚举法的 Python 版本非常短import math x0, y0 map(int, input().split()) if y0 % x0 ! 0: print(0) else: n y0 // x0 ans 0 i 1 while i * i n: if n % i 0: j n // i if math.gcd(i, j) 1: ans 1 if i j else 2 i 1 print(ans)用 Java 的话注意把乘法写成1L * x0 * y0以及Math.gcd在 Java 里需要自己写或者用BigInteger其他没有区别。这套“先数学化简、再编码实现”的思路在任何语言里都是通用的。4. 实操中的坑与调试心得4.1 前置特判y0 能不能整除 x0这是我反复强调的一点。数学上gcd(P, Q)一定整除lcm(P, Q)因为最小公倍数是最大公约数的倍数。所以输入x04, y010这种数据时答案必然是0没有任何数对满足条件。如果不做这个特判三种解法里至少两种会出问题质因数分解法里n y0 / x0会直接把10 / 4算成2丢掉了余数然后对着错误的结果输出一个2^k。约数对枚举法同样会基于错误的n做出错误的计数。暴力法倒是不会错因为它会老老实实枚举并验证但还是会做一堆无用功浪费那点性能。所以别偷懒在代码最前面写上if (y0 % x0 ! 0) { cout 0; return 0; }这一句能省很多事。4.2 int 溢出看不见的杀手这道题数据范围是x0, y0 ≤ 100000看起来不大但乘法算起来却能轻松突破int上限x0 * y0最大是10^10而int上限约2.1×10^9。如果你写int q x0 * y0 / p;中间乘法就已经溢出了算出来的q是错的。如果你写for (int i 1; i * i n; i)当i接近几万时i * i也可能溢出。正确的写法是乘法前加1LL或(long long)强制类型转换例如1LL * x0 * y0。循环条件写i n / i或者用(long long)i * i n。这个溢出问题是很多“AC 代码在本地跑得好好的、一提交就 WA”的罪魁祸首。刷题多了你会发现凡是涉及乘法的题目第一件事就是先评估中间结果会不会超int。4.3 有序数对 vs 无序数对样例已经给了答案这个坑我开头提过这里再展开说。题目统计的是所有可能的两个正整数P, Q的个数从样例输出来看(12,15)和(15,12)是两个独立方案所以是有序数对。对应到代码在约数对枚举法中i ! j时执行ans 2因为(i, j)和(j, i)都合法。在质因数分解法中2^k天然就是有序计数因为每个质因子归属a还是归属b算作不同方案。在暴力法中每次枚举P都只验证一份由于P遍历了所有可能值Q自然也跟着遍历所以能正确计到有序对。如果你一开始按无序数对理解写出了ans而不是ans 2样例就会输出2而不是4。这是判断“算法理解是否正确”的一道标杆。4.4 常见错误速查表错误类型具体表现解决办法忘记特判整除x04, y010 时输出非0开头加if (y0 % x0 ! 0)输出0乘法溢出暴力法算 q 时 WA用1LL * x0 * y0提升到 long long循环条件溢出i*i 在 i 较大时溢变负数死循环改成i n / i计数只加1样例输出2而非4约数对法i ! j时ans 2质因数分解不除干净cnt 统计错误答案偏大内层while (n % i 0) n / i除到不能再除这几条基本覆盖了我见过的所有 P1029 提交错误。如果你提交 WA 了优先对照这张表自查大概率能在三十秒内找到问题。5. 从 P1029 延伸出去的通用数论套路5.1 遇到 gcd/lcm 题先写公式再动手做多了你会发现gcd/lcm 类题目的解题路径相当固定基本是四步走写出乘积关系gcd(P,Q) * lcm(P,Q) P * Q先用公式把未知数串起来。化出互质条件令P g * aQ g * b推出gcd(a,b)1把两个约束压缩成一个约束。分类讨论如果题目变成“乘积固定、互质数对计数”不是枚举约数就是质因子分配如果题目还带着别的条件就继续往下拆。处理边界先想清楚0解、1解、大数溢出这些边界情况再写循环。这套打法可以直接套到洛谷 P1072《Hankson 的趣味题》上。那道题给定了gcd(x, a0) a1和lcm(x, b0) b1形式上比 P1029 更复杂但核心思路依然是“先拆成互质、再枚举候选 x”只是要枚举的维度多了一层。去刷那道题时你会发现 P1029 教会你的那套推导方法完全够用只需要在验证环节多做几次 gcd 而已。5.2 一个由 P1029 引发的思考题给你留一个课后思考如果题目改成“统计满足条件的P Q的无序数对个数”答案应该是多少结合质因数分解的结论有序答案是2^k。其中除了k0时只有(1,1)这一对外其余(a,b)都满足a ≠ b因此它们两两配对恰好一半满足a b。所以无序答案就是k 0时答案0k ≥ 1时答案2^(k-1)统一写就是(2^k - 1) / 2。你可以自己验证一下样例k2无序答案是(4-1)/2 1对应(12,15)那一组。这个变化在竞赛里很常见题目稍微改一两个字计数方式就要跟着变。理解了这个“从有序到无序”的转换以后再看到类似题目就不会乱了。5.3 练习路线建议刷完 P1029建议按这个顺序巩固P1072 Hankson 的趣味题同样是 gcd/lcm 条件反推综合性更强能检验你是背会了套路还是真正理解了原理。P3383 线性筛素数质因数分解的前置技能学会线性筛之后遇到n很大的质因子统计会更从容。P1835 素数密度区间素数问题性质和质因数分解相关能让你对“枚举约数”和“筛法本质”有更深的理解。这几题一路刷下来数论入门阶段的地基基本就打牢了。回头再看 P1029你会发现它真的不难难的是你愿不愿意静下心推一遍公式。我个人第一次做这道题的时候用的就是暴力枚举跑样例倒是过了交上去也 AC 了但心里总觉得自己在碰运气没底。后来看到2^k那种计数解法才意识到自己绕了远路。现在再看这类数论题我的习惯是先掏出公式推五分钟推不动再考虑暴力。你也别嫌推导麻烦数论题的魅力就在这儿每当你用一个简洁公式替换掉一大段循环那种快感是暴力过题完全比不上的。先把暴力写出来验证思路再想优化再回头品一品公式的由来这道 P1029 才算真正吃透了。 
长河君 · 2026/10/9 9:29:00 · 阅读 1.2k P1029最大公约数最小公倍数：从暴力枚举到质因数分解计数
聊一道洛谷上的经典普及组题——P1029题名《最大公约数和最小公倍数问题》来自 NOIP2001 普及组。题目本身很短读一遍就能懂什么意思但真要动手写很多人第一次都会卡在怎么枚举、怎么计数上。我见过不少同学对着样例3 60输出4一头雾水想不明白(12,15)和(15,12)为什么算两组。如果你也有这个疑惑这篇题解就是为你准备的。先说结论这道题值得认真做三遍。第一遍用暴力过样例第二遍用约数枚举优化第三遍用质因数分解把它变成一道组合计数题。三遍下来你对最大公约数、最小公倍数、互质这三个概念的理解基本就超过一大半刷题人了。整篇文章我会从题目拆解、数学推导、三种代码实现、常见坑位、扩展套路五个部分展开新手可以直接照着代码抄有基础的人也可以重点看第二章的推导和第五章的延伸。1. 题目拆解P1029 到底在考察什么1.1 题干回顾与样例分析题目要求很直白输入两个正整数x0, y0求出所有满足以下条件的正整数对(P, Q)的个数P, Q的最大公约数是x0P, Q的最小公倍数是y0样例给的是x0 3, y0 60输出4。看到这个4不妨手动枚举一下符合条件的数对(3, 60)gcd(3,60)3lcm(3,60)60成立(12, 15)gcd(12,15)3lcm(12,15)60成立(15, 12)同样成立(60, 3)同样成立所以答案是4。注意这里(12,15)和(15,12)被当成了两个不同的方案也就是说题目统计的是有序数对。这一点很容易被忽略很多新手按照“两个数一组”去计数得出2交上去就 WA 了。后面第三章的代码里我会专门说明计数时为什么要加2。1.2 核心考点拆解这道题表面上是“给定最大公约数和最小公倍数反求数对”实际上考察了四个基础能力最大公约数与最小公倍数的关系它们不是独立的中间隔着一条核心公式gcd * lcm P * Q能不能想到这条公式决定了你是暴力枚举还是优雅计数。互质判断把P, Q同时除以x0之后剩下的两个数必须互质。这个结论是整套解法的灵魂。枚举上界的确定很多人第一反应是两层循环枚举P和Q但P和Q的范围可以到十万人次双层循环直接超时。能不能把枚举范围压缩到√n甚至完全不用枚举是区分“暴力选手”和“数学选手”的分水岭。特殊数据的处理比如x0不能整除y0时答案直接是0再比如x0 y0时答案只有1。这些边界情况不做特判很容易写出“样例能过、提交全错”的代码。说白了这题不考任何高深算法考的是你对数论基础概念的理解是否到位以及能不能把理解转化成代码。想通这一层你后面再看任何 gcd/lcm 相关的题目都会顺手很多。2. 数学原理三个关键公式帮你建立解题直觉2.1 最大公约数与最小公倍数的乘积关系第一个要刻进脑子里的公式是gcd(P, Q) * lcm(P, Q) P * Q这个公式在竞赛数论里几乎天天见。简单证明一下令g gcd(P, Q)那么可以写成P g * aQ g * b其中a和b互质。此时最小公倍数就是g * a * b。于是gcd(P, Q) * lcm(P, Q) g * (g * a * b) g² * a * b (g * a) * (g * b) P * Q这个结论成立的关键在于a和b互质。如果a和b还有公共因子那g就不是最大公约数公式也就不成立了。有了这条公式这道题就多了一个思路既然P * Q x0 * y0那么只要枚举P就能直接算出Q x0 * y0 / P不用再两层循环了。但要注意这只是第一步优化真正的数学解法比这还要优雅。2.2 变量替换把问题改成“互质数对乘积固定”接下来做一步关键替换。因为条件里说了gcd(P, Q) x0所以P和Q必然是x0的倍数。于是可以设P x0 * aQ x0 * b那么gcd(P, Q) x0 * gcd(a, b)这个结论可以验证提取公因子后互质的部分不会影响 gcd。题目要求gcd(P, Q) x0所以必然有gcd(a, b) 1也就是a和b互质。再看lcm(P, Q)。因为P和Q中都含有一个共同的x0且a、b互质所以lcm(P, Q) x0 * a * b题目要求lcm(P, Q) y0于是得到x0 * a * b y0即a * b y0 / x0这一步做完题目就完全变了一个样子求有多少对互质的正整数(a, b)使得它们的乘积等于y0 / x0。这个转换的好处是巨大的。原本P和Q是两个独立的未知数现在它们的关系被压缩成了“乘积固定”这一条原本要判断 gcd 和 lcm 两个条件现在只要判断互质一个条件。后面所有解法本质都是在处理“互质数对乘积固定”这个问题。2.3 质因数分配把枚举题变成计数题如果只要求“乘积固定”那方法就是枚举约数但如果还要求“互质”就可以进一步用质因数分解来思考。假设n y0 / x0把n做质因数分解n p1^e1 * p2^e2 * ... * pk^ek其中p1, p2, ..., pk是互不相同的质因子。现在要找互质的a, b满足a * b n。关键来了因为a和b互质同一个质因子不能同时出现在a和b里否则它们就有公共因子了。所以对于每个质因子pi^ei它的全部幂次只能整体分给a或者整体分给b绝不能拆分。每个质因子有 2 种归属一共有k个不同质因子所以合法的(a, b)有序对数量就是2^k拿样例验证x03, y060n202²×5不同质因子个数k2答案就是2²4。和输出完全一致。这个推导相当漂亮它把一道“找到所有数对再逐个验证”的题目压缩成了一行1 k的计算。做竞赛题多了你会发现很多“枚举题”背后都藏着类似的组合计数逻辑找到它代码量能少一个量级。3. 三种解法的完整实现3.1 解法一质因数分解 组合计数最推荐既然第二章已经推出了2^k这个结论代码实现就非常直接先判断y0能不能整除x0能的话对n y0 / x0做质因数分解统计不同质因子个数输出1 k。#include bits/stdc.h using namespace std; int main() { int x0, y0; cin x0 y0; // 关键特判gcd 必须整除 lcm否则无解 if (y0 % x0 ! 0) { cout 0 endl; return 0; } int n y0 / x0; int cnt 0; // 统计不同质因子的个数 // 质因数分解注意循环条件用 i n / i 防止溢出 for (int i 2; i n / i; i) { if (n % i 0) { cnt; // 遇到一个新的质因子 while (n % i 0) { n / i; // 把这个质因子全部除干净 } } } // 如果 n 还剩下一个大于1的数说明它是一个大质因子 if (n 1) cnt; cout (1 cnt) endl; return 0; }逐段解释一下先做y0 % x0的特判。这一步不是锦上添花而是必需。如果x0不能整除y0后面n y0 / x0会丢掉余数算出来的答案全是错的。数学上gcd(P,Q)必须整除lcm(P,Q)所以这个特判的语义是“无解直接输出0”。质因数分解用i n / i而不是i * i n原因是i * i在i很大的时候可能溢出int写成除法更安全。这在竞赛里是一个非常常见的细节坑。1 cnt中的cnt最大也就 6 左右因为n 100000而2×3×5×7×11×13 30030再乘一个 17 就超过十万了所以完全不用担心移位溢出。这个解法的复杂度是O(√n)n最大十万的量级也只有几百次运算跑起来是毫秒级。代码短、思路清晰是我最推荐的一种写法。3.2 解法二约数对枚举 gcd 判断最容易理解如果你觉得“质因子分配”的跳跃有点大没问题还有一条更直白的路直接枚举n的所有约数对(i, j)判断i和j是否互质。互质就计数不互质就跳过。#include bits/stdc.h using namespace std; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int main() { int x0, y0; cin x0 y0; if (y0 % x0 ! 0) { cout 0 endl; return 0; } int n y0 / x0; int ans 0; // 只枚举到 sqrt(n)另一半约数可以对称得到 for (int i 1; i n / i; i) { if (n % i 0) { int j n / i; if (gcd(i, j) 1) { if (i j) { ans 1; // i j 只有 ij1 这一种情况 } else { ans 2; // (i,j) 和 (j,i) 都合法 } } } } cout ans endl; return 0; }这个做法背后的逻辑是a * b n的每一对互质约数都对应一组(P, Q)。因为P x0 * aQ x0 * b所以枚举i从 1 到√nj n / i天然覆盖了所有约数对。为什么i ! j时加 2因为题目算的是有序数对a4, b5对应(P,Q)(12,15)而a5, b4对应(15,12)它们是两个不同的答案。只有i j 1这种特殊情况交换后还是同一对所以只加 1。复杂度是O(√n log n)多出来的log n来自每次 gcd 的辗转相除。实际运行起来依然飞快而且比质因数分解法更容易让新手理解“为什么互质就能计数”。如果你是在给别人讲题我建议先用这个解法打底再引出 2^k 的组合计数。3.3 解法三暴力枚举 乘积关系新手的保底方案第三种方法最朴素但也不能说没用——当你实在推不出来的时候至少还有一条路能 AC。思路就是用P * Q x0 * y0这个公式枚举P为x0的倍数算出Q x0 * y0 / P然后检查gcd(P, Q)是否等于x0且lcm(P, Q)是否等于y0。#include bits/stdc.h using namespace std; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } long long lcm(int a, int b) { return 1LL * a / gcd(a, b) * b; // 先除后乘避免溢出 } int main() { int x0, y0; cin x0 y0; int ans 0; // P 必须是 x0 的倍数且 P 的范围在 x0 到 y0 之间 for (int p x0; p y0; p x0) { if ((1LL * x0 * y0) % p ! 0) continue; // 必须整除否则 Q 不是整数 int q 1LL * x0 * y0 / p; if (gcd(p, q) x0 lcm(p, q) y0) { ans; } } cout ans endl; return 0; }这个解法的时间复杂度是O(y0 / x0 * log y0)。最坏情况是x02, y0100000时循环约五万次每次做两次 gcd总操作量在百万级别洛谷评测机完全跑得动。但这里有两个致命细节必须注意1LL * x0 * y0一定要用long long。x0 * y0最大是10^10直接乘会爆int。q也要用int接住因为x0 * y0 / p的值实际上不会超过y0的范围但中间过程的乘法必须先提升到long long。暴力的好处是逻辑简单、不容易写错适合在考场上一筹莫展时保底用。坏处是它没有利用互质条件代码里同时判断了 gcd 和 lcm逻辑上有一点冗余而且当数据范围放大到百万甚至千万级别时它就跑不动了。所以它只能算“保底方案”不是“最优方案”。3.4 三种方法对比与语言迁移三种方法放在一起看差异一目了然解法核心思想时间复杂度代码量适合场景质因数分解法互质等价于质因子整体分配O(√n)最短竞赛正解推荐掌握约数对枚举法枚举约数对 gcd 判断O(√n log n)中等最易理解适合讲题暴力枚举法PQx0y0 逐个验证O((y0/x0) log y0)中等保底方案新手可写如果用的是 Python算法思路完全一样只是语法不同。约数对枚举法的 Python 版本非常短import math x0, y0 map(int, input().split()) if y0 % x0 ! 0: print(0) else: n y0 // x0 ans 0 i 1 while i * i n: if n % i 0: j n // i if math.gcd(i, j) 1: ans 1 if i j else 2 i 1 print(ans)用 Java 的话注意把乘法写成1L * x0 * y0以及Math.gcd在 Java 里需要自己写或者用BigInteger其他没有区别。这套“先数学化简、再编码实现”的思路在任何语言里都是通用的。4. 实操中的坑与调试心得4.1 前置特判y0 能不能整除 x0这是我反复强调的一点。数学上gcd(P, Q)一定整除lcm(P, Q)因为最小公倍数是最大公约数的倍数。所以输入x04, y010这种数据时答案必然是0没有任何数对满足条件。如果不做这个特判三种解法里至少两种会出问题质因数分解法里n y0 / x0会直接把10 / 4算成2丢掉了余数然后对着错误的结果输出一个2^k。约数对枚举法同样会基于错误的n做出错误的计数。暴力法倒是不会错因为它会老老实实枚举并验证但还是会做一堆无用功浪费那点性能。所以别偷懒在代码最前面写上if (y0 % x0 ! 0) { cout 0; return 0; }这一句能省很多事。4.2 int 溢出看不见的杀手这道题数据范围是x0, y0 ≤ 100000看起来不大但乘法算起来却能轻松突破int上限x0 * y0最大是10^10而int上限约2.1×10^9。如果你写int q x0 * y0 / p;中间乘法就已经溢出了算出来的q是错的。如果你写for (int i 1; i * i n; i)当i接近几万时i * i也可能溢出。正确的写法是乘法前加1LL或(long long)强制类型转换例如1LL * x0 * y0。循环条件写i n / i或者用(long long)i * i n。这个溢出问题是很多“AC 代码在本地跑得好好的、一提交就 WA”的罪魁祸首。刷题多了你会发现凡是涉及乘法的题目第一件事就是先评估中间结果会不会超int。4.3 有序数对 vs 无序数对样例已经给了答案这个坑我开头提过这里再展开说。题目统计的是所有可能的两个正整数P, Q的个数从样例输出来看(12,15)和(15,12)是两个独立方案所以是有序数对。对应到代码在约数对枚举法中i ! j时执行ans 2因为(i, j)和(j, i)都合法。在质因数分解法中2^k天然就是有序计数因为每个质因子归属a还是归属b算作不同方案。在暴力法中每次枚举P都只验证一份由于P遍历了所有可能值Q自然也跟着遍历所以能正确计到有序对。如果你一开始按无序数对理解写出了ans而不是ans 2样例就会输出2而不是4。这是判断“算法理解是否正确”的一道标杆。4.4 常见错误速查表错误类型具体表现解决办法忘记特判整除x04, y010 时输出非0开头加if (y0 % x0 ! 0)输出0乘法溢出暴力法算 q 时 WA用1LL * x0 * y0提升到 long long循环条件溢出i*i 在 i 较大时溢变负数死循环改成i n / i计数只加1样例输出2而非4约数对法i ! j时ans 2质因数分解不除干净cnt 统计错误答案偏大内层while (n % i 0) n / i除到不能再除这几条基本覆盖了我见过的所有 P1029 提交错误。如果你提交 WA 了优先对照这张表自查大概率能在三十秒内找到问题。5. 从 P1029 延伸出去的通用数论套路5.1 遇到 gcd/lcm 题先写公式再动手做多了你会发现gcd/lcm 类题目的解题路径相当固定基本是四步走写出乘积关系gcd(P,Q) * lcm(P,Q) P * Q先用公式把未知数串起来。化出互质条件令P g * aQ g * b推出gcd(a,b)1把两个约束压缩成一个约束。分类讨论如果题目变成“乘积固定、互质数对计数”不是枚举约数就是质因子分配如果题目还带着别的条件就继续往下拆。处理边界先想清楚0解、1解、大数溢出这些边界情况再写循环。这套打法可以直接套到洛谷 P1072《Hankson 的趣味题》上。那道题给定了gcd(x, a0) a1和lcm(x, b0) b1形式上比 P1029 更复杂但核心思路依然是“先拆成互质、再枚举候选 x”只是要枚举的维度多了一层。去刷那道题时你会发现 P1029 教会你的那套推导方法完全够用只需要在验证环节多做几次 gcd 而已。5.2 一个由 P1029 引发的思考题给你留一个课后思考如果题目改成“统计满足条件的P Q的无序数对个数”答案应该是多少结合质因数分解的结论有序答案是2^k。其中除了k0时只有(1,1)这一对外其余(a,b)都满足a ≠ b因此它们两两配对恰好一半满足a b。所以无序答案就是k 0时答案0k ≥ 1时答案2^(k-1)统一写就是(2^k - 1) / 2。你可以自己验证一下样例k2无序答案是(4-1)/2 1对应(12,15)那一组。这个变化在竞赛里很常见题目稍微改一两个字计数方式就要跟着变。理解了这个“从有序到无序”的转换以后再看到类似题目就不会乱了。5.3 练习路线建议刷完 P1029建议按这个顺序巩固P1072 Hankson 的趣味题同样是 gcd/lcm 条件反推综合性更强能检验你是背会了套路还是真正理解了原理。P3383 线性筛素数质因数分解的前置技能学会线性筛之后遇到n很大的质因子统计会更从容。P1835 素数密度区间素数问题性质和质因数分解相关能让你对“枚举约数”和“筛法本质”有更深的理解。这几题一路刷下来数论入门阶段的地基基本就打牢了。回头再看 P1029你会发现它真的不难难的是你愿不愿意静下心推一遍公式。我个人第一次做这道题的时候用的就是暴力枚举跑样例倒是过了交上去也 AC 了但心里总觉得自己在碰运气没底。后来看到2^k那种计数解法才意识到自己绕了远路。现在再看这类数论题我的习惯是先掏出公式推五分钟推不动再考虑暴力。你也别嫌推导麻烦数论题的魅力就在这儿每当你用一个简洁公式替换掉一大段循环那种快感是暴力过题完全比不上的。先把暴力写出来验证思路再想优化再回头品一品公式的由来这道 P1029 才算真正吃透了。