1. 项目概述与问题核心最近在洛谷上刷到一道经典老题P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题。这道题别看它挂着“普及组”的标签很多刚接触数论和编程的朋友第一次做很容易掉进暴力枚举的陷阱里然后喜提一个TLE超时。我当年也在这道题上卡过壳后来琢磨透了发现它的核心其实是一个巧妙的数学转化理解了之后代码写起来非常优雅效率也极高。今天就来详细拆解一下这道题不仅告诉你怎么写更要讲清楚为什么这么写以及如何从题目描述一步步推导出最优解。题目的大意是给定两个正整数x0,y0我们知道存在两个正整数P,Q满足P和Q的最大公约数GCD是x0最小公倍数LCM是y0。现在的问题是像这样的(P, Q)有序数对即(P, Q)和(Q, P)算作两种除非PQ一共有多少种可能举个例子如果x03,y060那么满足条件的数对有(3, 60),(15, 12),(12, 15),(60, 3)这4对。你的任务就是写个程序输入x0和y0输出这样的数对个数。最直接的想法也是最初的陷阱就是暴力枚举。既然P和Q最小是x0因为公约数至少是x0最大不会超过y0因为公倍数至少是y0那就从x0到y0双重循环枚举P和Q检查每一对的gcd(P, Q)是否等于x0且lcm(P, Q)是否等于y0。这个思路绝对正确但复杂度是 O(n²)对于y0最大可以到 10^9 的数据范围来说是绝对不可能跑完的。我们必须寻找更聪明的办法。2. 数学原理深度解析与思路转化2.1 最大公约数与最小公倍数的本质联系要跳出暴力枚举关键在于理解 GCD 和 LCM 之间一个非常核心的数学关系。对于任意两个正整数a和b有下面这个公式始终成立a * b gcd(a, b) * lcm(a, b)这个公式是解决本题的钥匙。我们来证明一下为什么。设g gcd(a, b)那么我们可以将a和b表示为a g * mb g * n其中m和n是互质的正整数即gcd(m, n) 1。这是因为g已经是最大的公约数了m和n不能再有大于1的公因子。此时a和b的最小公倍数l必须包含g以及m和n的所有质因子。由于m和n互质它们没有公共质因子所以l g * m * n。现在计算a * ba * b (g * m) * (g * n) g² * m * n再计算g * lg * l g * (g * m * n) g² * m * n看两者完全相等。所以a * b gcd(a, b) * lcm(a, b)恒成立。2.2 将原问题转化为搜索互质因子对回到我们的问题。我们已知gcd(P, Q) x0lcm(P, Q) y0。根据上面的公式立刻有P * Q x0 * y0这是一个非常重要的约束条件。我们设k x0 * y0。结合最大公约数的定义我们依然可以设P x0 * aQ x0 * b其中a和b是互质的正整数即gcd(a, b) 1。现在我们把P和Q代入乘积公式(x0 * a) * (x0 * b) x0 * y0x0² * a * b x0 * y0两边同时除以x0x0为正整数肯定大于0x0 * a * b y0因此a * b y0 / x0我们得到了一个更简洁的等式。令t y0 / x0。这里有一个关键前提y0必须能被x0整除。因为x0是P和Q的公约数而y0是P和Q的公倍数公倍数一定是公约数的整数倍。如果输入数据中y0 % x0 ! 0那么答案直接就是0不存在这样的P,Q。现在问题转化了我们需要找到所有互质的正整数对(a, b)使得a * b t。并且每一对互质的(a, b)都唯一对应回原问题的一对(P, Q)P x0 * aQ x0 * b因为a和b互质所以gcd(P, Q) x0 * gcd(a, b) x0 * 1 x0满足条件。同时lcm(P, Q) x0 * a * b x0 * t y0也满足条件。注意这里a和b是正整数所以t也必须为正整数这再次要求y0是x0的倍数。2.3 搜索范围的极大优化原始问题需要枚举P和Q范围在[x0, y0]非常大。转化后的问题只需要枚举a而a是t的因子。t y0 / x0。y0最大为 2,000,000,00020亿x0最小为 1所以t最大也可能达到 20亿。直接枚举1到t来找因子仍然是 O(t)对于 20亿来说还是太慢。但是枚举因子有更高效的方法。我们只需要枚举到sqrt(t)即可。因为如果a是t的因子那么必然存在另一个因子b t / a。我们只需要让a从1循环到sqrt(t)向下取整对于每一个能整除t的a我们就可以得到一对因子(a, b)其中b t / a。这样时间复杂度就从 O(t) 降到了 O(√t)。对于t最大为 20亿sqrt(20亿)大约在 44721 左右这个计算量对于计算机来说就是一瞬间的事情。3. 算法设计与实现细节3.1 核心算法流程基于上面的数学推导我们可以梳理出清晰的算法步骤输入与初步判断读入两个正整数x0和y0。合法性检查如果y0不能被x0整除则直接输出0并结束程序。因为不存在满足条件的数对。计算中间变量计算t y0 / x0。枚举因子并检查互质初始化计数器ans 0。让变量a从1循环到sqrt(t)包含等于。 a. 判断a是否能整除t即t % a 0。如果不能跳过。 b. 如果能整除则计算b t / a。 c. 检查a和b是否互质即gcd(a, b) 1。 d. 如果互质则说明找到了一组有效的(a, b)。这一组(a, b)对应原问题的两组解(Px0*a, Qx0*b)和(Px0*b, Qx0*a)除非a b。 e. 因此如果a ! b计数器ans增加 2如果a b这只会在t是完全平方数且a是sqrt(t)时发生计数器ans增加 1。输出结果输出计数器ans的值。3.2 关键代码实现与解释这里给出用 C 实现的核心代码片段并附上详细注释。#include iostream #include cmath // 用于 sqrt 函数 using namespace std; // 辗转相除法求最大公约数 long long gcd(long long a, long long b) { while (b ! 0) { long long temp b; b a % b; a temp; } return a; } int main() { long long x0, y0; cin x0 y0; // 检查合法性y0 必须是 x0 的倍数 if (y0 % x0 ! 0) { cout 0 endl; return 0; } long long t y0 / x0; // 计算乘积 t a * b long long ans 0; // 枚举因子 a只需枚举到 sqrt(t) for (long long a 1; a * a t; a) { if (t % a 0) { // 如果 a 是 t 的因子 long long b t / a; // 计算对应的因子 b // 关键判断a 和 b 必须互质 if (gcd(a, b) 1) { // 一对互质的 (a, b) 对应两对 (P, Q)除非 a b if (a b) { ans 1; // 例如 ab1, PQx0 } else { ans 2; // (P,Q) 和 (Q,P) 算两种 } } } } cout ans endl; return 0; }代码要点解析数据类型使用long long。因为x0和y0最大为 2e9它们的乘积x0*y0可能达到 4e18超出了int的表示范围约21亿。虽然在我们的算法中不会直接计算这个乘积但使用long long是更安全的做法避免潜在的溢出问题。gcd函数实现了经典的辗转相除法欧几里得算法效率很高用于判断a和b是否互质。循环条件a * a t这比a sqrt(t)更常用因为它避免了浮点数运算和类型转换是整数循环中判断平方根的惯用写法。互质判断是核心if (gcd(a, b) 1)这一行是算法的灵魂。它确保了由a,b还原出的P,Q的最大公约数恰好是x0。如果没有这个条件仅仅找到因子对(a, b)那么gcd(P, Q)将会是x0 * gcd(a, b)大于x0不满足题意。计数逻辑当a ! b时(a,b)和(b,a)是两种不同的有序对对应原问题中(P,Q)和(Q,P)。当a b时两者是同一个有序对只算一次。3.3 一个完整的计算示例让我们手动模拟一下x03,y060的情况。检查60 % 3 0合法。计算t 60 / 3 20。枚举a从 1 到sqrt(20)≈4。a1:20%10,b20/120。gcd(1,20)1互质。1!20ans2。此时对应(P3*13, Q3*2060)和(P60, Q3)。a2:20%20,b10。gcd(2,10)2不互质跳过。a3:20%3!0跳过。a4:20%40,b5。gcd(4,5)1互质。4!5ans2。此时对应(P3*412, Q3*515)和(P15, Q12)。a5: 循环条件a*a20(2520) 为假循环结束。注意a5和b4的情况已经在a4时被处理过了这正是只枚举到sqrt(t)的原因。最终ans 4输出4。结果正确。4. 边界条件与常见错误排查4.1 必须处理的边界情况y0不是x0的倍数这是首要检查项。如果y0 % x0 ! 0答案就是0。例如输入(2, 7)直接输出0。x0 y0的情况此时t y0/x0 1。sqrt(1)1循环中只有a1。t%10b1。gcd(1,1)1且ab所以ans1。最终答案为1对应的唯一数对是(Px0, Qx0)。这是正确的。t为完全平方数且sqrt(t)对应的a,b互质如x01, y09则t9。循环中a3时b3gcd(3,3)3 !1不互质所以不会计数。实际上对于t9因子对有(1,9)和(3,3)。(1,9)互质计数2(3,3)不互质不计数。最终答案为2对应(1,9)和(9,1)。我们的代码能正确处理。大数运算与溢出这是最容易忽略的错误。即使y0在int范围内t y0 / x0也在int范围内但为了安全起见以及良好的习惯建议将所有相关变量x0,y0,t,a,ans都声明为long long。尤其是在计算a * a时如果a是int而t接近int上限a*a可能导致溢出使得循环条件判断错误。4.2 常见错误与调试技巧错误现象可能原因排查与解决方法答案比预期少忘记了y0 % x0 ! 0的判断或者判断了但逻辑写反。仔细检查第一个if条件确保是if (y0 % x0 ! 0)。答案比预期少很多gcd函数实现有误或者没有判断a和b是否互质。单独测试gcd函数。确认循环体内有if (gcd(a, b) 1)的判断。答案比预期多计数逻辑错误。当a b时也加了2。检查计数部分应该是if (a b) ans1; else ans2;。超时 (TLE)使用了暴力双重循环枚举P和Q。必须使用本文介绍的数学优化方法只枚举t的因子到sqrt(t)。结果错误小数据对大数据错变量类型用int导致大数乘法a*a或x0*y0时溢出。将所有相关变量改为long long。编译错误使用了sqrt函数但未包含cmath头文件。添加#include cmath。更推荐使用a * a t的循环条件。实操心得在写这类数论题时“先数学后代码”的原则非常重要。不要一上来就想着怎么循环。先拿出纸笔把题目给出的条件gcd(P,Q)x0,lcm(P,Q)y0和已知的数学定理P*Q gcd* lcm写下来进行推导。往往推导几步之后一个复杂度大大降低的新问题就会浮现出来。这道题就是一个完美的例子它将一个看似需要枚举P、Q两个变量的问题转化为了只需要枚举t的因子并检查互质性的单变量问题。5. 算法扩展与性能分析5.1 为什么枚举到 sqrt(t) 就足够了这是一个常见的优化技巧。对于任意一个正整数t它的因子总是成对出现的如果a是t的因子那么b t / a也一定是t的因子。并且对于每一对因子(a, b)必然有a b或b a。当我们从1开始枚举a时b会从t开始逐渐减小。当a超过sqrt(t)时我们得到的因子对(a, b)中的a必然会大于b。但是请注意此时的(a, b)本质上就是之前某个(b, a)的重复。例如t20a1得到(1,20)a4得到(4,5)。当a5时得到(5,4)这已经和a4时得到的(4,5)是同一对因子只是顺序不同。而我们的算法在a4时已经同时处理了(4,5)和(5,4)这两种顺序通过ans2。因此枚举到sqrt(t)足以覆盖所有不重复的因子对组合避免了重复计算。5.2 时间复杂度分析我们算法的主要耗时部分在于for循环和循环内的gcd计算。循环次数约为sqrt(t)次。每次循环的操作一次取模运算t % a一次除法t / a一次gcd函数调用。gcd函数的时间复杂度辗转相除法的时间复杂度可以近似认为是 O(log min(a, b))。在本题中a和b最大约为t所以单次gcd复杂度约为 O(log t)。因此总的时间复杂度约为 O(√t * log t)。对于t最大为 20亿√t ≈ 44721log t ≈ 31总的操作次数大约在 140 万次左右这对于现代计算机来说完全是瞬间完成的。5.3 进一步的优化思路针对更大数据范围虽然本题数据范围下 O(√t) 的算法已经足够快但我们不妨思考一下如果t变得极大比如 10^15√t也会达到 3千多万此时循环可能就有压力了。有没有更快的办法答案是肯定的核心在于质因数分解。回顾我们的目标找到所有互质的正整数对(a, b)使得a * b t。 如果我们将t进行质因数分解t p1^c1 * p2^c2 * ... * pk^ck。 那么对于每一个质因子pi它的指数ci必须全部分配给a或者全部分配给b才能保证a和b互质因为如果pi同时分给a和b一点a和b就会有公因子pi。所以对于k个不同的质因子每个质因子都有 2 种分配选择全部给a或全部给b。因此总的互质因子对(a, b)的数量就是2^k。注意这里(a, b)和(b, a)被视为不同的有序对。所以最终的答案ans就是2^k。当a b时即所有指数都平均分配这只在所有指数ci均为偶数即t是完全平方数时才可能发生但此时a和b不互质因为它们包含相同的质因子所以这种情况不会被计入2^k中与我们之前算法的计数逻辑一致。举例t 60 2^2 * 3^1 * 5^1。质因子有2, 3, 5共k3个。互质因子对的数量为2^3 8。我们可以列出来 (1, 60), (4, 15), (3, 20), (12, 5), (5, 12), (20, 3), (15, 4), (60, 1)。正好8对。算法改进基于质因数分解的算法步骤如下计算t y0 / x0。对t进行质因数分解统计不同质因子的个数k。答案ans 1 k即 2 的 k 次方。这个算法的时间复杂度主要取决于质因数分解的速度。使用试除法分解质因数是 O(√t)和之前一样。但如果t很大我们可以使用更高效的 Pollard-Rho 算法。不过对于竞赛和日常应用试除法在t 10^12时通常可以接受。个人体会这道题从暴力枚举到利用数学性质优化为枚举因子再到利用数论知识直接通过质因数个数计算答案体现了算法优化层层递进的美感。在面试或者实际解决问题时即使最终不需要实现最高效的版本能清晰地阐述出这几种思路的演进也足以展示你扎实的数学功底和算法思维。对于洛谷 P1029枚举因子的方法已经完全够用且易于实现是性价比最高的选择。
1. 项目概述与问题核心最近在洛谷上刷到一道经典老题P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题。这道题别看它挂着“普及组”的标签很多刚接触数论和编程的朋友第一次做很容易掉进暴力枚举的陷阱里然后喜提一个TLE超时。我当年也在这道题上卡过壳后来琢磨透了发现它的核心其实是一个巧妙的数学转化理解了之后代码写起来非常优雅效率也极高。今天就来详细拆解一下这道题不仅告诉你怎么写更要讲清楚为什么这么写以及如何从题目描述一步步推导出最优解。题目的大意是给定两个正整数x0,y0我们知道存在两个正整数P,Q满足P和Q的最大公约数GCD是x0最小公倍数LCM是y0。现在的问题是像这样的(P, Q)有序数对即(P, Q)和(Q, P)算作两种除非PQ一共有多少种可能举个例子如果x03,y060那么满足条件的数对有(3, 60),(15, 12),(12, 15),(60, 3)这4对。你的任务就是写个程序输入x0和y0输出这样的数对个数。最直接的想法也是最初的陷阱就是暴力枚举。既然P和Q最小是x0因为公约数至少是x0最大不会超过y0因为公倍数至少是y0那就从x0到y0双重循环枚举P和Q检查每一对的gcd(P, Q)是否等于x0且lcm(P, Q)是否等于y0。这个思路绝对正确但复杂度是 O(n²)对于y0最大可以到 10^9 的数据范围来说是绝对不可能跑完的。我们必须寻找更聪明的办法。2. 数学原理深度解析与思路转化2.1 最大公约数与最小公倍数的本质联系要跳出暴力枚举关键在于理解 GCD 和 LCM 之间一个非常核心的数学关系。对于任意两个正整数a和b有下面这个公式始终成立a * b gcd(a, b) * lcm(a, b)这个公式是解决本题的钥匙。我们来证明一下为什么。设g gcd(a, b)那么我们可以将a和b表示为a g * mb g * n其中m和n是互质的正整数即gcd(m, n) 1。这是因为g已经是最大的公约数了m和n不能再有大于1的公因子。此时a和b的最小公倍数l必须包含g以及m和n的所有质因子。由于m和n互质它们没有公共质因子所以l g * m * n。现在计算a * ba * b (g * m) * (g * n) g² * m * n再计算g * lg * l g * (g * m * n) g² * m * n看两者完全相等。所以a * b gcd(a, b) * lcm(a, b)恒成立。2.2 将原问题转化为搜索互质因子对回到我们的问题。我们已知gcd(P, Q) x0lcm(P, Q) y0。根据上面的公式立刻有P * Q x0 * y0这是一个非常重要的约束条件。我们设k x0 * y0。结合最大公约数的定义我们依然可以设P x0 * aQ x0 * b其中a和b是互质的正整数即gcd(a, b) 1。现在我们把P和Q代入乘积公式(x0 * a) * (x0 * b) x0 * y0x0² * a * b x0 * y0两边同时除以x0x0为正整数肯定大于0x0 * a * b y0因此a * b y0 / x0我们得到了一个更简洁的等式。令t y0 / x0。这里有一个关键前提y0必须能被x0整除。因为x0是P和Q的公约数而y0是P和Q的公倍数公倍数一定是公约数的整数倍。如果输入数据中y0 % x0 ! 0那么答案直接就是0不存在这样的P,Q。现在问题转化了我们需要找到所有互质的正整数对(a, b)使得a * b t。并且每一对互质的(a, b)都唯一对应回原问题的一对(P, Q)P x0 * aQ x0 * b因为a和b互质所以gcd(P, Q) x0 * gcd(a, b) x0 * 1 x0满足条件。同时lcm(P, Q) x0 * a * b x0 * t y0也满足条件。注意这里a和b是正整数所以t也必须为正整数这再次要求y0是x0的倍数。2.3 搜索范围的极大优化原始问题需要枚举P和Q范围在[x0, y0]非常大。转化后的问题只需要枚举a而a是t的因子。t y0 / x0。y0最大为 2,000,000,00020亿x0最小为 1所以t最大也可能达到 20亿。直接枚举1到t来找因子仍然是 O(t)对于 20亿来说还是太慢。但是枚举因子有更高效的方法。我们只需要枚举到sqrt(t)即可。因为如果a是t的因子那么必然存在另一个因子b t / a。我们只需要让a从1循环到sqrt(t)向下取整对于每一个能整除t的a我们就可以得到一对因子(a, b)其中b t / a。这样时间复杂度就从 O(t) 降到了 O(√t)。对于t最大为 20亿sqrt(20亿)大约在 44721 左右这个计算量对于计算机来说就是一瞬间的事情。3. 算法设计与实现细节3.1 核心算法流程基于上面的数学推导我们可以梳理出清晰的算法步骤输入与初步判断读入两个正整数x0和y0。合法性检查如果y0不能被x0整除则直接输出0并结束程序。因为不存在满足条件的数对。计算中间变量计算t y0 / x0。枚举因子并检查互质初始化计数器ans 0。让变量a从1循环到sqrt(t)包含等于。 a. 判断a是否能整除t即t % a 0。如果不能跳过。 b. 如果能整除则计算b t / a。 c. 检查a和b是否互质即gcd(a, b) 1。 d. 如果互质则说明找到了一组有效的(a, b)。这一组(a, b)对应原问题的两组解(Px0*a, Qx0*b)和(Px0*b, Qx0*a)除非a b。 e. 因此如果a ! b计数器ans增加 2如果a b这只会在t是完全平方数且a是sqrt(t)时发生计数器ans增加 1。输出结果输出计数器ans的值。3.2 关键代码实现与解释这里给出用 C 实现的核心代码片段并附上详细注释。#include iostream #include cmath // 用于 sqrt 函数 using namespace std; // 辗转相除法求最大公约数 long long gcd(long long a, long long b) { while (b ! 0) { long long temp b; b a % b; a temp; } return a; } int main() { long long x0, y0; cin x0 y0; // 检查合法性y0 必须是 x0 的倍数 if (y0 % x0 ! 0) { cout 0 endl; return 0; } long long t y0 / x0; // 计算乘积 t a * b long long ans 0; // 枚举因子 a只需枚举到 sqrt(t) for (long long a 1; a * a t; a) { if (t % a 0) { // 如果 a 是 t 的因子 long long b t / a; // 计算对应的因子 b // 关键判断a 和 b 必须互质 if (gcd(a, b) 1) { // 一对互质的 (a, b) 对应两对 (P, Q)除非 a b if (a b) { ans 1; // 例如 ab1, PQx0 } else { ans 2; // (P,Q) 和 (Q,P) 算两种 } } } } cout ans endl; return 0; }代码要点解析数据类型使用long long。因为x0和y0最大为 2e9它们的乘积x0*y0可能达到 4e18超出了int的表示范围约21亿。虽然在我们的算法中不会直接计算这个乘积但使用long long是更安全的做法避免潜在的溢出问题。gcd函数实现了经典的辗转相除法欧几里得算法效率很高用于判断a和b是否互质。循环条件a * a t这比a sqrt(t)更常用因为它避免了浮点数运算和类型转换是整数循环中判断平方根的惯用写法。互质判断是核心if (gcd(a, b) 1)这一行是算法的灵魂。它确保了由a,b还原出的P,Q的最大公约数恰好是x0。如果没有这个条件仅仅找到因子对(a, b)那么gcd(P, Q)将会是x0 * gcd(a, b)大于x0不满足题意。计数逻辑当a ! b时(a,b)和(b,a)是两种不同的有序对对应原问题中(P,Q)和(Q,P)。当a b时两者是同一个有序对只算一次。3.3 一个完整的计算示例让我们手动模拟一下x03,y060的情况。检查60 % 3 0合法。计算t 60 / 3 20。枚举a从 1 到sqrt(20)≈4。a1:20%10,b20/120。gcd(1,20)1互质。1!20ans2。此时对应(P3*13, Q3*2060)和(P60, Q3)。a2:20%20,b10。gcd(2,10)2不互质跳过。a3:20%3!0跳过。a4:20%40,b5。gcd(4,5)1互质。4!5ans2。此时对应(P3*412, Q3*515)和(P15, Q12)。a5: 循环条件a*a20(2520) 为假循环结束。注意a5和b4的情况已经在a4时被处理过了这正是只枚举到sqrt(t)的原因。最终ans 4输出4。结果正确。4. 边界条件与常见错误排查4.1 必须处理的边界情况y0不是x0的倍数这是首要检查项。如果y0 % x0 ! 0答案就是0。例如输入(2, 7)直接输出0。x0 y0的情况此时t y0/x0 1。sqrt(1)1循环中只有a1。t%10b1。gcd(1,1)1且ab所以ans1。最终答案为1对应的唯一数对是(Px0, Qx0)。这是正确的。t为完全平方数且sqrt(t)对应的a,b互质如x01, y09则t9。循环中a3时b3gcd(3,3)3 !1不互质所以不会计数。实际上对于t9因子对有(1,9)和(3,3)。(1,9)互质计数2(3,3)不互质不计数。最终答案为2对应(1,9)和(9,1)。我们的代码能正确处理。大数运算与溢出这是最容易忽略的错误。即使y0在int范围内t y0 / x0也在int范围内但为了安全起见以及良好的习惯建议将所有相关变量x0,y0,t,a,ans都声明为long long。尤其是在计算a * a时如果a是int而t接近int上限a*a可能导致溢出使得循环条件判断错误。4.2 常见错误与调试技巧错误现象可能原因排查与解决方法答案比预期少忘记了y0 % x0 ! 0的判断或者判断了但逻辑写反。仔细检查第一个if条件确保是if (y0 % x0 ! 0)。答案比预期少很多gcd函数实现有误或者没有判断a和b是否互质。单独测试gcd函数。确认循环体内有if (gcd(a, b) 1)的判断。答案比预期多计数逻辑错误。当a b时也加了2。检查计数部分应该是if (a b) ans1; else ans2;。超时 (TLE)使用了暴力双重循环枚举P和Q。必须使用本文介绍的数学优化方法只枚举t的因子到sqrt(t)。结果错误小数据对大数据错变量类型用int导致大数乘法a*a或x0*y0时溢出。将所有相关变量改为long long。编译错误使用了sqrt函数但未包含cmath头文件。添加#include cmath。更推荐使用a * a t的循环条件。实操心得在写这类数论题时“先数学后代码”的原则非常重要。不要一上来就想着怎么循环。先拿出纸笔把题目给出的条件gcd(P,Q)x0,lcm(P,Q)y0和已知的数学定理P*Q gcd* lcm写下来进行推导。往往推导几步之后一个复杂度大大降低的新问题就会浮现出来。这道题就是一个完美的例子它将一个看似需要枚举P、Q两个变量的问题转化为了只需要枚举t的因子并检查互质性的单变量问题。5. 算法扩展与性能分析5.1 为什么枚举到 sqrt(t) 就足够了这是一个常见的优化技巧。对于任意一个正整数t它的因子总是成对出现的如果a是t的因子那么b t / a也一定是t的因子。并且对于每一对因子(a, b)必然有a b或b a。当我们从1开始枚举a时b会从t开始逐渐减小。当a超过sqrt(t)时我们得到的因子对(a, b)中的a必然会大于b。但是请注意此时的(a, b)本质上就是之前某个(b, a)的重复。例如t20a1得到(1,20)a4得到(4,5)。当a5时得到(5,4)这已经和a4时得到的(4,5)是同一对因子只是顺序不同。而我们的算法在a4时已经同时处理了(4,5)和(5,4)这两种顺序通过ans2。因此枚举到sqrt(t)足以覆盖所有不重复的因子对组合避免了重复计算。5.2 时间复杂度分析我们算法的主要耗时部分在于for循环和循环内的gcd计算。循环次数约为sqrt(t)次。每次循环的操作一次取模运算t % a一次除法t / a一次gcd函数调用。gcd函数的时间复杂度辗转相除法的时间复杂度可以近似认为是 O(log min(a, b))。在本题中a和b最大约为t所以单次gcd复杂度约为 O(log t)。因此总的时间复杂度约为 O(√t * log t)。对于t最大为 20亿√t ≈ 44721log t ≈ 31总的操作次数大约在 140 万次左右这对于现代计算机来说完全是瞬间完成的。5.3 进一步的优化思路针对更大数据范围虽然本题数据范围下 O(√t) 的算法已经足够快但我们不妨思考一下如果t变得极大比如 10^15√t也会达到 3千多万此时循环可能就有压力了。有没有更快的办法答案是肯定的核心在于质因数分解。回顾我们的目标找到所有互质的正整数对(a, b)使得a * b t。 如果我们将t进行质因数分解t p1^c1 * p2^c2 * ... * pk^ck。 那么对于每一个质因子pi它的指数ci必须全部分配给a或者全部分配给b才能保证a和b互质因为如果pi同时分给a和b一点a和b就会有公因子pi。所以对于k个不同的质因子每个质因子都有 2 种分配选择全部给a或全部给b。因此总的互质因子对(a, b)的数量就是2^k。注意这里(a, b)和(b, a)被视为不同的有序对。所以最终的答案ans就是2^k。当a b时即所有指数都平均分配这只在所有指数ci均为偶数即t是完全平方数时才可能发生但此时a和b不互质因为它们包含相同的质因子所以这种情况不会被计入2^k中与我们之前算法的计数逻辑一致。举例t 60 2^2 * 3^1 * 5^1。质因子有2, 3, 5共k3个。互质因子对的数量为2^3 8。我们可以列出来 (1, 60), (4, 15), (3, 20), (12, 5), (5, 12), (20, 3), (15, 4), (60, 1)。正好8对。算法改进基于质因数分解的算法步骤如下计算t y0 / x0。对t进行质因数分解统计不同质因子的个数k。答案ans 1 k即 2 的 k 次方。这个算法的时间复杂度主要取决于质因数分解的速度。使用试除法分解质因数是 O(√t)和之前一样。但如果t很大我们可以使用更高效的 Pollard-Rho 算法。不过对于竞赛和日常应用试除法在t 10^12时通常可以接受。个人体会这道题从暴力枚举到利用数学性质优化为枚举因子再到利用数论知识直接通过质因数个数计算答案体现了算法优化层层递进的美感。在面试或者实际解决问题时即使最终不需要实现最高效的版本能清晰地阐述出这几种思路的演进也足以展示你扎实的数学功底和算法思维。对于洛谷 P1029枚举因子的方法已经完全够用且易于实现是性价比最高的选择。
)
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
