1. 从一道题说起因子链与数论直觉最近在准备蓝桥杯国赛刷题时遇到一道很有意思的数论题叫“X的因子链”。题目大意是给定一个正整数X我们要构造一个尽可能长的序列序列的第一个数是1最后一个数是X并且序列中后一个数必须是前一个数的倍数。同时序列中除了1和X以外的所有数都必须是X的因子。问这样的最长序列有多少条初看题目可能会有点懵。序列要长后一项是前一项的倍数中间项还得是X的因子……这听起来有点像在X的因子集合里找一条“倍数关系”的路径并且要尽可能长。直觉告诉我这肯定和X的质因数分解脱不了干系。数论题嘛尤其是蓝桥杯国赛级别的往往不会让你真的去暴力枚举所有因子和排列背后一定有巧妙的数学原理可以大幅简化计算。这道题的核心其实就是对“算术基本定理”和“线性筛质数”这两个基础但强大的工具的一次深度应用和思维体操。今天我就结合自己的解题过程把里面的门道掰开揉碎了讲清楚你会发现看似复杂的组合问题最终会归结为一个优雅的排列数计算。2. 算术基本定理拆解问题的基石要理解“X的因子链”首先得彻底搞懂X的因子是怎么来的。这就不得不提数论的“基石”——算术基本定理。算术基本定理告诉我们任何一个大于1的自然数都可以唯一地分解成有限个质数的乘积。这里的“唯一”是指如果不考虑质因数的排列顺序那么这种分解方式是唯一的。用公式表示就是X p1^a1 * p2^a2 * ... * pk^ak其中p1, p2, ..., pk是互不相同的质数a1, a2, ..., ak是正整数表示对应质因数的指数。这个定理为什么是基石因为它完全决定了X的所有因子。X的任意一个正因子d其质因数分解必然是这样的形式d p1^b1 * p2^b2 * ... * pk^bk其中对于每一个i指数bi的取值范围是0 bi ai。举个例子假设X 12。分解质因数12 2^2 * 3^1。 那么12的所有因子1, 2, 3, 4, 6, 12就可以通过分配指数得到1 2^0 * 3^02 2^1 * 3^03 2^0 * 3^14 2^2 * 3^06 2^1 * 3^112 2^2 * 3^1看到这里你应该能发现因子和质因数指数向量(b1, b2, ..., bk)是一一对应的。这个对应关系是解决本题的关键。现在回到我们的“因子链”问题。链的要求是1 d0, d1, d2, ..., dm X且d(i)是d(i-1)的倍数同时d1, ..., d(m-1)都是X的因子。倍数关系意味着什么如果d(i)是d(i-1)的倍数那么d(i) / d(i-1)是一个大于1的整数。从质因数分解的角度看这意味着在从d(i-1)到d(i)的过程中某些质因数的指数增加了至少增加1而其他质因数的指数保持不变或也增加。更关键的是由于链上的每个数都是X的因子所以它们的指数向量(b1, b2, ..., bk)都满足0 bj aj。并且序列从(0,0,...,0)对应数字1开始到(a1, a2, ..., ak)对应数字X结束。每一步我们只能选择某一个质因数pj将其指数bj增加1因为要保证后一个是前一个的倍数且增长的步长最小化才能让链最长这里先埋个伏笔。于是整个“构造最长因子链”的问题被完美地转化了我们有k种不同的“质因数球”第j种球有aj个。我们需要把这些球排成一列。排球的顺序就对应了因子链增长的顺序。每次拿到一个第j种球就意味着我们将X的因子中质因数pj的指数增加了1。这样构造出来的序列其对应的数字序列一定是满足题目要求的因子链并且链的长度是固定的m a1 a2 ... ak 1。这里的“1”是因为起点1全0指数也算一个。这个长度就是最长可能长度因为我们把X的所有质因数指数从0增长到满额每一步只增长1这已经是最细致的增长方式了不可能更长了。所以第一个问题的答案最长因子链的长度L (a1 a2 ... ak) 1。3. 线性筛质数高效获取质因数分解在将问题转化为“排列质因数球”之后我们面临一个更前置的、也是算法题中的经典问题如何对给定的X快速地进行质因数分解得到所有的pi和ai对于单次查询我们当然可以用试除法从2遍历到sqrt(X)。但题目往往会有多组测试数据或者X本身很大比如10^6甚至更大这时O(sqrt(X))的复杂度可能就吃不消了。蓝桥杯对效率是有要求的这就需要我们提前进行预处理。这就是线性筛质数欧拉筛大显身手的地方。线性筛可以在O(n)的时间复杂度内筛选出1到n之间的所有质数。但它的威力不止于此经过巧妙改造我们可以让它同时求出每个数的最小质因数Least Prime Factor, LPF。有了最小质因数我们对任意数X进行质因数分解的复杂度就从O(sqrt(X))降到了O(log X)。让我解释一下这背后的原理和操作。3.1 标准线性筛欧拉筛的原理普通的埃氏筛时间复杂度是O(n log log n)核心思想是标记每个质数的倍数。但它有个问题一个合数会被它的所有质因子重复标记比如6会被2和3各标记一次。线性筛通过一个关键优化保证了每个合数只被其最小质因数标记一次。算法步骤如下用代码逻辑描述更清晰初始化一个布尔数组is_prime[0..n]全部为true一个空列表primes存放质数。从i 2遍历到n a. 如果is_prime[i]为true则将i加入primes列表。 b. 遍历已有的质数列表primes设当前质数为p - 计算next i * p。 - 如果next n跳出循环。 - 标记is_prime[next] false。 -关键判断如果i % p 0则跳出内层循环。这保证了next这个合数是被其最小质因数p筛掉的。最后这个if (i % p 0) break;是精髓。因为i能被p整除说明p是i的最小质因数我们从小到大遍历质数表。那么对于后续更大的质数pi * p的最小质因数依然是p而不是p。这个合数应该留给未来某个i此时i是i * p / p与p相乘时来标记以保证“最小质因数标记”的原则。3.2 改造以记录最小质因数LPF为了加速质因数分解我们需要一个数组lpf[N]其中lpf[x]存储数字x的最小质因数。 在筛法的标记步骤中当我们确定next i * p将被筛掉时我们就知道了next的最小质因数是p。所以我们可以直接设置lpf[next] p。 对于质数i本身其最小质因数就是它自己所以lpf[i] i。改造后的核心代码片段C风格如下const int N 1000000; // 根据数据范围设定 vectorint primes; int lpf[N1]; bool is_prime[N1]; void linear_sieve(int n) { fill(is_prime, is_prime n 1, true); for (int i 2; i n; i) { if (is_prime[i]) { primes.push_back(i); lpf[i] i; // 质数的最小质因数是自身 } for (int p : primes) { long long next 1LL * i * p; if (next n) break; is_prime[next] false; lpf[next] p; // 记录合数 next 的最小质因数是 p if (i % p 0) break; // 关键保证每个合数只被最小质因数筛一次 } } }3.3 利用LPF进行快速质因数分解有了lpf数组分解任意x (1 x N)就变得异常高效初始化一个空列表或映射factors用于存储质因数及其指数。while (x 1): a. 取出p lpf[x]。 b. 在factors中将质因数p的计数加1。 c.x x / p。循环结束factors中就存储了x的所有质因数及其指数。这个过程的时间复杂度是O(k)其中k是x的质因数个数重复的算多个。由于每次循环x至少除以2所以循环次数不超过log2(x)非常快。实操心得在算法竞赛中如果题目数据范围明确比如X 10^6并且涉及大量数的质因数分解提前用线性筛预处理lpf数组是标准操作。这属于典型的“空间换时间”并且这个空间开销一个int数组通常是可接受的。自己实现一遍线性筛并理解if (i % p 0) break;这一行是掌握数论算法基础的重要一步。4. 多重集排列数计算最长链的数目现在我们已经知道最长因子链的构造过程等价于将所有的“质因数球”一个多重集排成一列。那么第二个问题最长链的数目就等价于求这个多重集的全排列数。什么是多重集就是元素可以重复的集合。比如我们的质因数集合有a1个p1a2个p2...ak个pk。多重集的全排列公式是总排列数 (总球数)! / (每种球数量的阶乘之积)即N (a1 a2 ... ak)! / (a1! * a2! * ... * ak!)这个公式直观上很好理解如果所有球都不同排列数就是(总球数)!。但现在有a1个相同的p1球它们在所有排列中互换位置不会产生新的排列所以要除以a1!来消除这种重复。对其他种类的球也是如此。在我们的问题中总球数就是所有质因数的指数之和记作total a1 a2 ... ak。这正是链的长度L - 1。所以最长因子链的数目Ans total! / (a1! * a2! * ... * ak!)。4.1 如何计算这个可能巨大的数这里又有一个坑。total可能很大total!的结果是一个天文数字远远超出任何基本数据类型的范围。题目通常会要求输出结果对一个特定的数M取模比如M 1e97或2^64自然溢出。蓝桥杯的这道题根据历年风格很可能要求输出具体数值不取模但数值会保证在long long64位整数范围内。这就要求我们不能直接计算阶乘然后相除因为中间结果会溢出。我们需要一种在计算过程中就能处理大数或者避免大数阶乘的方法。方法一边乘边除利用整数除法由于最终答案一定是整数我们可以设计一个循环从1累乘到total但在乘的过程中尽可能早地除以分母中各ai!的因子。我们可以预处理出分母中所有需要被除掉的数即所有1到ai的每个数然后在对分子累乘时一旦当前乘积能被某个分母的因子整除就立即除。这需要维护一个分母因子的数组并不断尝试约分。方法二组合数学公式与递推其实total! / (a1! * a2! * ... * ak!)这个式子有深刻的组合意义。它可以理解为有total个位置我们先从中选a1个位置放p1有C(total, a1)种选法然后从剩下的total - a1个位置中选a2个位置放p2有C(total - a1, a2)种选法依此类推。 根据乘法原理Ans C(total, a1) * C(total - a1, a2) * ... * C(ak, ak)其中C(n, m)是组合数。组合数C(n, m) n! / (m! * (n-m)!)。虽然也要算阶乘但我们可以用递推公式或预处理阶乘与逆元在取模意义下的方式来高效计算。对于不取模、保证结果在long long内的情况我们可以用C(n, m) C(n-1, m-1) C(n-1, m)的递推公式动态规划计算一个较小的组合数表因为total不会特别大或者直接用乘法与除法交替计算单个组合数并注意使用long long防止中间溢出。4.2 一个完整的计算示例假设X 12 2^2 * 3^1。 则a12 (对应质数2), a21 (对应质数3)。total a1 a2 3。 最长链长度L total 1 4。 最长链数目Ans 3! / (2! * 1!) 6 / (2 * 1) 3。我们可以验证一下。所有“质因数球”是{2, 2, 3}。 其所有排列为2, 2, 32, 3, 23, 2, 2每一种排列对应一条最长因子链。以排列2, 3, 2为例起始数字1指数向量 (0, 0)第一步拿到一个“2”球指数向量变为 (1, 0)对应数字 2^1 * 3^0 2第二步拿到一个“3”球指数向量变为 (1, 1)对应数字 2^1 * 3^1 6第三步拿到一个“2”球指数向量变为 (2, 1)对应数字 2^2 * 3^1 12 所以对应的因子链是1 - 2 - 6 - 12。另外两种排列对应链1-2-4-12 和 1-3-6-12。正好是3条。注意事项在计算排列数时务必注意数据范围和溢出问题。如果题目明确不取模要确保你的计算路径无论是边乘边除还是递推组合数中所有的中间结果和最终结果都在long long最大值约9e18范围内。对于total较大的情况边乘边除需要精心设计约分顺序否则中间乘积可能溢出。一个稳妥的做法是将分子分母都分解质因数统计每个质因数的总指数然后直接计算这个质因数乘积这样每一步都是乘法只要最终结果不溢出即可。5. 算法实现与细节雕琢理论清晰了接下来就是把思路转化成代码。这里我给出一个完整的、注重效率和鲁棒性的C实现框架并逐一解释关键细节。5.1 数据结构与预处理首先我们需要根据X的最大可能值比如题目给定的上限MAX_X来初始化线性筛。#include iostream #include vector #include map #include algorithm using namespace std; const int MAX_X 1000000; // 假设题目中X最大为1e6 vectorint primes; int lpf[MAX_X 1]; bool is_prime[MAX_X 1]; void init() { fill(is_prime, is_prime MAX_X 1, true); for (int i 2; i MAX_X; i) { if (is_prime[i]) { primes.push_back(i); lpf[i] i; } for (int p : primes) { long long next 1LL * i * p; if (next MAX_X) break; is_prime[next] false; lpf[next] p; if (i % p 0) break; } } }5.2 质因数分解函数利用lpf数组快速分解。// 返回一个映射key是质因数value是指数 mapint, int factorize(int x) { mapint, int factors; while (x 1) { int p lpf[x]; factors[p]; // 对应质因数指数加1 x / p; } return factors; }使用map可以自动按质因数大小排序方便后续处理虽然对本题计算来说顺序无关。5.3 计算排列数不取模保证不溢出这里采用“边乘边除”的策略并假设最终答案在long long范围内。我们需要计算total! / (a1! * a2! * ... * ak!)。 一个技巧是准备一个分母因子的列表然后对分子从1乘到total每乘一个数i就遍历分母列表如果能整除某个分母因子d则i / d并将该d从列表中移除或标记为已使用。但这样效率较低O(total * k)。更高效且不易出错的方法是将分母的每个阶乘展开成连续的整数然后与分子的连续整数进行“约分”。我们可以模拟一个分数乘法Ans 1for i from 1 to total:Ans * ifor 每个质因数种类j:while (aj 0 且 Ans % (aj的当前值) 0):Ans / ajaj--但这样写逻辑有点乱且aj被修改了。更好的实现是用一个数组denom存放所有需要被除掉的数即所有1,2,...,a1, 1,2,...,a2, ...。然后计算分子连乘时不断与denom中的数约分。long long calculate_permutations(const mapint, int factors) { vectorint denom; // 存放所有分母的因子 int total 0; for (auto [p, cnt] : factors) { total cnt; for (int v 1; v cnt; v) { denom.push_back(v); // 将 cnt! 展开为 1,2,...,cnt } } long long ans 1; for (int numerator 1; numerator total; numerator) { ans * numerator; // 乘以分子的一个因子 // 尝试用分母列表中的数约分ans for (int d : denom) { if (d 1 ans % d 0) { ans / d; d 1; // 该分母因子已被约掉标记为1 } } } // 理论上循环结束后denom中所有数都应被约分为1 return ans; }这个实现清晰且易于理解。时间复杂度是O(total * (total的质因数种类数))在total不大比如小于30时完全可行。这也是本题的隐含条件因为total是质因数指数和对于X 10^6total不会太大因为2^20就超过100万了所以total最多20左右。5.4 主逻辑与完整代码框架将以上部分组合起来。int main() { init(); // 预处理线性筛 int x; while (cin x) { // 假设有多组测试数据 if (x 1) { // 特殊情况1的因子只有1最长链就是 1 - 1长度为1数量为1 cout 1 1 endl; continue; } mapint, int factors factorize(x); int total 0; for (auto [p, cnt] : factors) { total cnt; } int length total 1; long long count calculate_permutations(factors); cout length count endl; } return 0; }5.5 边界情况与测试X 1这是一个特例。1没有质因数。按照定义因子链只有[1]长度为1数量为1。我们的质因数分解函数对x1会返回空映射total0length1但在计算排列数时分母和分子都是空积视为1所以count应该是1。需要在计算函数或主逻辑中单独处理或者确保calculate_permutations对空输入返回1。X 是质数假设X p则factors {p:1}total1length2。排列数计算1! / 1! 1。对应因子链只有一条1 - p。符合直觉。X 是质数的幂假设X p^k则factors {p:k}totalklengthk1。排列数计算k! / k! 1。这是因为所有“球”都相同只有一种排列方式。对应的最长链是唯一的1 - p - p^2 - ... - p^k。常规合数如前文的X12应输出4 3。踩坑实录在实现calculate_permutations时我最开始犯了一个错误。我试图先计算分子total!和每个分母ai!然后相除。即使使用long long20!的值约为2.43e18已经接近long long的上限9.22e18。如果total再大一点或者先乘后除的顺序不对中间结果就溢出了。所以“边乘边除”或者“质因数统计法”是必须的。另外对于X1的特例一定要处理否则在计算total和遍历分母时会出错。6. 思维延伸与举一反三解决了具体的题目我们不妨把思维再拔高一点看看这个“因子链”模型和相关的数学工具还能用在什么地方。6.1 与格路问题的联系“多重集排列”问题有一个经典的组合解释从坐标原点(0,0,...,0)走到点(a1, a2, ..., ak)每次只能沿着某个坐标轴的正方向走一步即增加一个对应质因数的指数。问有多少种不同的路径这其实就是我们因子链的数目。每一步的选择增加哪个质因数的指数对应路径中的一个决策。这样的路径数正是多重集排列数。这建立了数论问题和组合几何问题的一个有趣桥梁。6.2 线性筛的更多应用我们这里只用线性筛来求最小质因数LPF。实际上线性筛是数论算法中的“瑞士军刀”经过改造它可以同时求出很多积性函数的值例如欧拉函数 φ(n)表示小于等于n且与n互质的数的个数。莫比乌斯函数 μ(n)用于莫比乌斯反演。约数个数函数 d(n)n的正约数个数。约数和函数 σ(n)n的所有正约数之和。其核心思想是在筛出合数i * p时根据i和p是否互质即i % p 0是否成立利用积性函数的性质可以由已知的f(i)和f(p)推导出f(i * p)。掌握这个技巧就能在O(n)时间内预处理出大量数论函数的前缀和这在解决复杂的数论求和问题时威力巨大。6.3 关于“最长”的严格性证明在我们之前的分析中我们默认了“每一步只增加一个质因数的指数1”的链是最长的。这需要一个小证明来让整个逻辑更严密。证明设X的质因数分解为p1^a1 * ... * pk^ak。对于任意一个满足题意的因子链1 d0, d1, ..., dm X考虑每个数对应的指数向量(b1, ..., bk)。从d(i-1)到d(i)由于d(i)是d(i-1)的倍数所以对于每个j有b_j(i) b_j(i-1)。并且因为d(i)是X的因子所以b_j(i) aj。 从全0向量到全aj向量每个分量bj需要从0增长到aj至少需要aj次增长。而每次增长即链中向前一步最多只能让所有bj中的某一个增加至少1实际上因为d(i)/d(i-1)是一个大于1的整数它至少包含一个质因数所以至少有一个bj增加了至少1。因此链的长度m从1开始算步数至少需要1 (a1 a2 ... ak)。而我们构造的“每次只增加一个质因数指数1”的链正好达到了这个下界因此它是最长的。这就严格证明了我们方法的正确性。6.4 如果问题变体允许中间项不是X的因子如果去掉“中间项必须是X的因子”这个条件只要求序列从1到X且后一项是前一项的倍数。那么最长链是什么样的此时我们可以在中间插入一些不是X因子的数。例如X12链可以是1 - 2 - 4 - 8 - 12其中8不是12的因子。这样链更长了吗并没有因为从4到8乘2从8到12乘1.5不是整数等等8到12是乘1.5不是整数倍哦这里错了。重新考虑1-2-4-8-12检查倍数关系2是1的2倍4是2的2倍8是4的2倍但12不是8的整数倍12/81.5。所以这个链不合法。实际上在只要求倍数关系的情况下最长链是每次乘以一个质数直到达到X的所有质因数。这等价于将X分解质因数后按任意顺序逐个乘上这些质因数。这又回到了我们最初的“质因数球”模型只不过现在“球”可以重复使用因为乘的质数可以不是X的因子不对最终乘积要等于X所以乘的质数必须是X的质因数且总次数等于指数。所以最长链的长度依然是total 1链的数目依然是多重集排列数。结论是在这个问题中“中间项是X的因子”这个条件对于最长链的长度和数量并没有增加额外的约束它只是确保了链上的所有数都在X的因子集合内这个性质。这是一个有趣的发现说明原题的条件设计得非常精巧既增加了题目的趣味性又没有改变最优化问题的数学本质。最后回顾整个解题过程从理解题意、转化问题算术基本定理到设计高效算法获取输入线性筛再到运用组合数学计算答案最后考虑边界和优化这是一道非常经典的、考察综合数论与组合思维的题目。它不要求高深的数学知识但需要对基础概念有深刻的理解和灵活的应用能力。在平时练习时多问几个“为什么”比如“为什么这样是最长”“这个公式是怎么来的”并动手实现、测试边界情况才能真正吃透这类题目在赛场上遇到变体也能游刃有余。 
长河君 · 2026/8/21 4:17:16 · 阅读 1.2k 从因子链问题解析算术基本定理与线性筛质数的应用
1. 从一道题说起因子链与数论直觉最近在准备蓝桥杯国赛刷题时遇到一道很有意思的数论题叫“X的因子链”。题目大意是给定一个正整数X我们要构造一个尽可能长的序列序列的第一个数是1最后一个数是X并且序列中后一个数必须是前一个数的倍数。同时序列中除了1和X以外的所有数都必须是X的因子。问这样的最长序列有多少条初看题目可能会有点懵。序列要长后一项是前一项的倍数中间项还得是X的因子……这听起来有点像在X的因子集合里找一条“倍数关系”的路径并且要尽可能长。直觉告诉我这肯定和X的质因数分解脱不了干系。数论题嘛尤其是蓝桥杯国赛级别的往往不会让你真的去暴力枚举所有因子和排列背后一定有巧妙的数学原理可以大幅简化计算。这道题的核心其实就是对“算术基本定理”和“线性筛质数”这两个基础但强大的工具的一次深度应用和思维体操。今天我就结合自己的解题过程把里面的门道掰开揉碎了讲清楚你会发现看似复杂的组合问题最终会归结为一个优雅的排列数计算。2. 算术基本定理拆解问题的基石要理解“X的因子链”首先得彻底搞懂X的因子是怎么来的。这就不得不提数论的“基石”——算术基本定理。算术基本定理告诉我们任何一个大于1的自然数都可以唯一地分解成有限个质数的乘积。这里的“唯一”是指如果不考虑质因数的排列顺序那么这种分解方式是唯一的。用公式表示就是X p1^a1 * p2^a2 * ... * pk^ak其中p1, p2, ..., pk是互不相同的质数a1, a2, ..., ak是正整数表示对应质因数的指数。这个定理为什么是基石因为它完全决定了X的所有因子。X的任意一个正因子d其质因数分解必然是这样的形式d p1^b1 * p2^b2 * ... * pk^bk其中对于每一个i指数bi的取值范围是0 bi ai。举个例子假设X 12。分解质因数12 2^2 * 3^1。 那么12的所有因子1, 2, 3, 4, 6, 12就可以通过分配指数得到1 2^0 * 3^02 2^1 * 3^03 2^0 * 3^14 2^2 * 3^06 2^1 * 3^112 2^2 * 3^1看到这里你应该能发现因子和质因数指数向量(b1, b2, ..., bk)是一一对应的。这个对应关系是解决本题的关键。现在回到我们的“因子链”问题。链的要求是1 d0, d1, d2, ..., dm X且d(i)是d(i-1)的倍数同时d1, ..., d(m-1)都是X的因子。倍数关系意味着什么如果d(i)是d(i-1)的倍数那么d(i) / d(i-1)是一个大于1的整数。从质因数分解的角度看这意味着在从d(i-1)到d(i)的过程中某些质因数的指数增加了至少增加1而其他质因数的指数保持不变或也增加。更关键的是由于链上的每个数都是X的因子所以它们的指数向量(b1, b2, ..., bk)都满足0 bj aj。并且序列从(0,0,...,0)对应数字1开始到(a1, a2, ..., ak)对应数字X结束。每一步我们只能选择某一个质因数pj将其指数bj增加1因为要保证后一个是前一个的倍数且增长的步长最小化才能让链最长这里先埋个伏笔。于是整个“构造最长因子链”的问题被完美地转化了我们有k种不同的“质因数球”第j种球有aj个。我们需要把这些球排成一列。排球的顺序就对应了因子链增长的顺序。每次拿到一个第j种球就意味着我们将X的因子中质因数pj的指数增加了1。这样构造出来的序列其对应的数字序列一定是满足题目要求的因子链并且链的长度是固定的m a1 a2 ... ak 1。这里的“1”是因为起点1全0指数也算一个。这个长度就是最长可能长度因为我们把X的所有质因数指数从0增长到满额每一步只增长1这已经是最细致的增长方式了不可能更长了。所以第一个问题的答案最长因子链的长度L (a1 a2 ... ak) 1。3. 线性筛质数高效获取质因数分解在将问题转化为“排列质因数球”之后我们面临一个更前置的、也是算法题中的经典问题如何对给定的X快速地进行质因数分解得到所有的pi和ai对于单次查询我们当然可以用试除法从2遍历到sqrt(X)。但题目往往会有多组测试数据或者X本身很大比如10^6甚至更大这时O(sqrt(X))的复杂度可能就吃不消了。蓝桥杯对效率是有要求的这就需要我们提前进行预处理。这就是线性筛质数欧拉筛大显身手的地方。线性筛可以在O(n)的时间复杂度内筛选出1到n之间的所有质数。但它的威力不止于此经过巧妙改造我们可以让它同时求出每个数的最小质因数Least Prime Factor, LPF。有了最小质因数我们对任意数X进行质因数分解的复杂度就从O(sqrt(X))降到了O(log X)。让我解释一下这背后的原理和操作。3.1 标准线性筛欧拉筛的原理普通的埃氏筛时间复杂度是O(n log log n)核心思想是标记每个质数的倍数。但它有个问题一个合数会被它的所有质因子重复标记比如6会被2和3各标记一次。线性筛通过一个关键优化保证了每个合数只被其最小质因数标记一次。算法步骤如下用代码逻辑描述更清晰初始化一个布尔数组is_prime[0..n]全部为true一个空列表primes存放质数。从i 2遍历到n a. 如果is_prime[i]为true则将i加入primes列表。 b. 遍历已有的质数列表primes设当前质数为p - 计算next i * p。 - 如果next n跳出循环。 - 标记is_prime[next] false。 -关键判断如果i % p 0则跳出内层循环。这保证了next这个合数是被其最小质因数p筛掉的。最后这个if (i % p 0) break;是精髓。因为i能被p整除说明p是i的最小质因数我们从小到大遍历质数表。那么对于后续更大的质数pi * p的最小质因数依然是p而不是p。这个合数应该留给未来某个i此时i是i * p / p与p相乘时来标记以保证“最小质因数标记”的原则。3.2 改造以记录最小质因数LPF为了加速质因数分解我们需要一个数组lpf[N]其中lpf[x]存储数字x的最小质因数。 在筛法的标记步骤中当我们确定next i * p将被筛掉时我们就知道了next的最小质因数是p。所以我们可以直接设置lpf[next] p。 对于质数i本身其最小质因数就是它自己所以lpf[i] i。改造后的核心代码片段C风格如下const int N 1000000; // 根据数据范围设定 vectorint primes; int lpf[N1]; bool is_prime[N1]; void linear_sieve(int n) { fill(is_prime, is_prime n 1, true); for (int i 2; i n; i) { if (is_prime[i]) { primes.push_back(i); lpf[i] i; // 质数的最小质因数是自身 } for (int p : primes) { long long next 1LL * i * p; if (next n) break; is_prime[next] false; lpf[next] p; // 记录合数 next 的最小质因数是 p if (i % p 0) break; // 关键保证每个合数只被最小质因数筛一次 } } }3.3 利用LPF进行快速质因数分解有了lpf数组分解任意x (1 x N)就变得异常高效初始化一个空列表或映射factors用于存储质因数及其指数。while (x 1): a. 取出p lpf[x]。 b. 在factors中将质因数p的计数加1。 c.x x / p。循环结束factors中就存储了x的所有质因数及其指数。这个过程的时间复杂度是O(k)其中k是x的质因数个数重复的算多个。由于每次循环x至少除以2所以循环次数不超过log2(x)非常快。实操心得在算法竞赛中如果题目数据范围明确比如X 10^6并且涉及大量数的质因数分解提前用线性筛预处理lpf数组是标准操作。这属于典型的“空间换时间”并且这个空间开销一个int数组通常是可接受的。自己实现一遍线性筛并理解if (i % p 0) break;这一行是掌握数论算法基础的重要一步。4. 多重集排列数计算最长链的数目现在我们已经知道最长因子链的构造过程等价于将所有的“质因数球”一个多重集排成一列。那么第二个问题最长链的数目就等价于求这个多重集的全排列数。什么是多重集就是元素可以重复的集合。比如我们的质因数集合有a1个p1a2个p2...ak个pk。多重集的全排列公式是总排列数 (总球数)! / (每种球数量的阶乘之积)即N (a1 a2 ... ak)! / (a1! * a2! * ... * ak!)这个公式直观上很好理解如果所有球都不同排列数就是(总球数)!。但现在有a1个相同的p1球它们在所有排列中互换位置不会产生新的排列所以要除以a1!来消除这种重复。对其他种类的球也是如此。在我们的问题中总球数就是所有质因数的指数之和记作total a1 a2 ... ak。这正是链的长度L - 1。所以最长因子链的数目Ans total! / (a1! * a2! * ... * ak!)。4.1 如何计算这个可能巨大的数这里又有一个坑。total可能很大total!的结果是一个天文数字远远超出任何基本数据类型的范围。题目通常会要求输出结果对一个特定的数M取模比如M 1e97或2^64自然溢出。蓝桥杯的这道题根据历年风格很可能要求输出具体数值不取模但数值会保证在long long64位整数范围内。这就要求我们不能直接计算阶乘然后相除因为中间结果会溢出。我们需要一种在计算过程中就能处理大数或者避免大数阶乘的方法。方法一边乘边除利用整数除法由于最终答案一定是整数我们可以设计一个循环从1累乘到total但在乘的过程中尽可能早地除以分母中各ai!的因子。我们可以预处理出分母中所有需要被除掉的数即所有1到ai的每个数然后在对分子累乘时一旦当前乘积能被某个分母的因子整除就立即除。这需要维护一个分母因子的数组并不断尝试约分。方法二组合数学公式与递推其实total! / (a1! * a2! * ... * ak!)这个式子有深刻的组合意义。它可以理解为有total个位置我们先从中选a1个位置放p1有C(total, a1)种选法然后从剩下的total - a1个位置中选a2个位置放p2有C(total - a1, a2)种选法依此类推。 根据乘法原理Ans C(total, a1) * C(total - a1, a2) * ... * C(ak, ak)其中C(n, m)是组合数。组合数C(n, m) n! / (m! * (n-m)!)。虽然也要算阶乘但我们可以用递推公式或预处理阶乘与逆元在取模意义下的方式来高效计算。对于不取模、保证结果在long long内的情况我们可以用C(n, m) C(n-1, m-1) C(n-1, m)的递推公式动态规划计算一个较小的组合数表因为total不会特别大或者直接用乘法与除法交替计算单个组合数并注意使用long long防止中间溢出。4.2 一个完整的计算示例假设X 12 2^2 * 3^1。 则a12 (对应质数2), a21 (对应质数3)。total a1 a2 3。 最长链长度L total 1 4。 最长链数目Ans 3! / (2! * 1!) 6 / (2 * 1) 3。我们可以验证一下。所有“质因数球”是{2, 2, 3}。 其所有排列为2, 2, 32, 3, 23, 2, 2每一种排列对应一条最长因子链。以排列2, 3, 2为例起始数字1指数向量 (0, 0)第一步拿到一个“2”球指数向量变为 (1, 0)对应数字 2^1 * 3^0 2第二步拿到一个“3”球指数向量变为 (1, 1)对应数字 2^1 * 3^1 6第三步拿到一个“2”球指数向量变为 (2, 1)对应数字 2^2 * 3^1 12 所以对应的因子链是1 - 2 - 6 - 12。另外两种排列对应链1-2-4-12 和 1-3-6-12。正好是3条。注意事项在计算排列数时务必注意数据范围和溢出问题。如果题目明确不取模要确保你的计算路径无论是边乘边除还是递推组合数中所有的中间结果和最终结果都在long long最大值约9e18范围内。对于total较大的情况边乘边除需要精心设计约分顺序否则中间乘积可能溢出。一个稳妥的做法是将分子分母都分解质因数统计每个质因数的总指数然后直接计算这个质因数乘积这样每一步都是乘法只要最终结果不溢出即可。5. 算法实现与细节雕琢理论清晰了接下来就是把思路转化成代码。这里我给出一个完整的、注重效率和鲁棒性的C实现框架并逐一解释关键细节。5.1 数据结构与预处理首先我们需要根据X的最大可能值比如题目给定的上限MAX_X来初始化线性筛。#include iostream #include vector #include map #include algorithm using namespace std; const int MAX_X 1000000; // 假设题目中X最大为1e6 vectorint primes; int lpf[MAX_X 1]; bool is_prime[MAX_X 1]; void init() { fill(is_prime, is_prime MAX_X 1, true); for (int i 2; i MAX_X; i) { if (is_prime[i]) { primes.push_back(i); lpf[i] i; } for (int p : primes) { long long next 1LL * i * p; if (next MAX_X) break; is_prime[next] false; lpf[next] p; if (i % p 0) break; } } }5.2 质因数分解函数利用lpf数组快速分解。// 返回一个映射key是质因数value是指数 mapint, int factorize(int x) { mapint, int factors; while (x 1) { int p lpf[x]; factors[p]; // 对应质因数指数加1 x / p; } return factors; }使用map可以自动按质因数大小排序方便后续处理虽然对本题计算来说顺序无关。5.3 计算排列数不取模保证不溢出这里采用“边乘边除”的策略并假设最终答案在long long范围内。我们需要计算total! / (a1! * a2! * ... * ak!)。 一个技巧是准备一个分母因子的列表然后对分子从1乘到total每乘一个数i就遍历分母列表如果能整除某个分母因子d则i / d并将该d从列表中移除或标记为已使用。但这样效率较低O(total * k)。更高效且不易出错的方法是将分母的每个阶乘展开成连续的整数然后与分子的连续整数进行“约分”。我们可以模拟一个分数乘法Ans 1for i from 1 to total:Ans * ifor 每个质因数种类j:while (aj 0 且 Ans % (aj的当前值) 0):Ans / ajaj--但这样写逻辑有点乱且aj被修改了。更好的实现是用一个数组denom存放所有需要被除掉的数即所有1,2,...,a1, 1,2,...,a2, ...。然后计算分子连乘时不断与denom中的数约分。long long calculate_permutations(const mapint, int factors) { vectorint denom; // 存放所有分母的因子 int total 0; for (auto [p, cnt] : factors) { total cnt; for (int v 1; v cnt; v) { denom.push_back(v); // 将 cnt! 展开为 1,2,...,cnt } } long long ans 1; for (int numerator 1; numerator total; numerator) { ans * numerator; // 乘以分子的一个因子 // 尝试用分母列表中的数约分ans for (int d : denom) { if (d 1 ans % d 0) { ans / d; d 1; // 该分母因子已被约掉标记为1 } } } // 理论上循环结束后denom中所有数都应被约分为1 return ans; }这个实现清晰且易于理解。时间复杂度是O(total * (total的质因数种类数))在total不大比如小于30时完全可行。这也是本题的隐含条件因为total是质因数指数和对于X 10^6total不会太大因为2^20就超过100万了所以total最多20左右。5.4 主逻辑与完整代码框架将以上部分组合起来。int main() { init(); // 预处理线性筛 int x; while (cin x) { // 假设有多组测试数据 if (x 1) { // 特殊情况1的因子只有1最长链就是 1 - 1长度为1数量为1 cout 1 1 endl; continue; } mapint, int factors factorize(x); int total 0; for (auto [p, cnt] : factors) { total cnt; } int length total 1; long long count calculate_permutations(factors); cout length count endl; } return 0; }5.5 边界情况与测试X 1这是一个特例。1没有质因数。按照定义因子链只有[1]长度为1数量为1。我们的质因数分解函数对x1会返回空映射total0length1但在计算排列数时分母和分子都是空积视为1所以count应该是1。需要在计算函数或主逻辑中单独处理或者确保calculate_permutations对空输入返回1。X 是质数假设X p则factors {p:1}total1length2。排列数计算1! / 1! 1。对应因子链只有一条1 - p。符合直觉。X 是质数的幂假设X p^k则factors {p:k}totalklengthk1。排列数计算k! / k! 1。这是因为所有“球”都相同只有一种排列方式。对应的最长链是唯一的1 - p - p^2 - ... - p^k。常规合数如前文的X12应输出4 3。踩坑实录在实现calculate_permutations时我最开始犯了一个错误。我试图先计算分子total!和每个分母ai!然后相除。即使使用long long20!的值约为2.43e18已经接近long long的上限9.22e18。如果total再大一点或者先乘后除的顺序不对中间结果就溢出了。所以“边乘边除”或者“质因数统计法”是必须的。另外对于X1的特例一定要处理否则在计算total和遍历分母时会出错。6. 思维延伸与举一反三解决了具体的题目我们不妨把思维再拔高一点看看这个“因子链”模型和相关的数学工具还能用在什么地方。6.1 与格路问题的联系“多重集排列”问题有一个经典的组合解释从坐标原点(0,0,...,0)走到点(a1, a2, ..., ak)每次只能沿着某个坐标轴的正方向走一步即增加一个对应质因数的指数。问有多少种不同的路径这其实就是我们因子链的数目。每一步的选择增加哪个质因数的指数对应路径中的一个决策。这样的路径数正是多重集排列数。这建立了数论问题和组合几何问题的一个有趣桥梁。6.2 线性筛的更多应用我们这里只用线性筛来求最小质因数LPF。实际上线性筛是数论算法中的“瑞士军刀”经过改造它可以同时求出很多积性函数的值例如欧拉函数 φ(n)表示小于等于n且与n互质的数的个数。莫比乌斯函数 μ(n)用于莫比乌斯反演。约数个数函数 d(n)n的正约数个数。约数和函数 σ(n)n的所有正约数之和。其核心思想是在筛出合数i * p时根据i和p是否互质即i % p 0是否成立利用积性函数的性质可以由已知的f(i)和f(p)推导出f(i * p)。掌握这个技巧就能在O(n)时间内预处理出大量数论函数的前缀和这在解决复杂的数论求和问题时威力巨大。6.3 关于“最长”的严格性证明在我们之前的分析中我们默认了“每一步只增加一个质因数的指数1”的链是最长的。这需要一个小证明来让整个逻辑更严密。证明设X的质因数分解为p1^a1 * ... * pk^ak。对于任意一个满足题意的因子链1 d0, d1, ..., dm X考虑每个数对应的指数向量(b1, ..., bk)。从d(i-1)到d(i)由于d(i)是d(i-1)的倍数所以对于每个j有b_j(i) b_j(i-1)。并且因为d(i)是X的因子所以b_j(i) aj。 从全0向量到全aj向量每个分量bj需要从0增长到aj至少需要aj次增长。而每次增长即链中向前一步最多只能让所有bj中的某一个增加至少1实际上因为d(i)/d(i-1)是一个大于1的整数它至少包含一个质因数所以至少有一个bj增加了至少1。因此链的长度m从1开始算步数至少需要1 (a1 a2 ... ak)。而我们构造的“每次只增加一个质因数指数1”的链正好达到了这个下界因此它是最长的。这就严格证明了我们方法的正确性。6.4 如果问题变体允许中间项不是X的因子如果去掉“中间项必须是X的因子”这个条件只要求序列从1到X且后一项是前一项的倍数。那么最长链是什么样的此时我们可以在中间插入一些不是X因子的数。例如X12链可以是1 - 2 - 4 - 8 - 12其中8不是12的因子。这样链更长了吗并没有因为从4到8乘2从8到12乘1.5不是整数等等8到12是乘1.5不是整数倍哦这里错了。重新考虑1-2-4-8-12检查倍数关系2是1的2倍4是2的2倍8是4的2倍但12不是8的整数倍12/81.5。所以这个链不合法。实际上在只要求倍数关系的情况下最长链是每次乘以一个质数直到达到X的所有质因数。这等价于将X分解质因数后按任意顺序逐个乘上这些质因数。这又回到了我们最初的“质因数球”模型只不过现在“球”可以重复使用因为乘的质数可以不是X的因子不对最终乘积要等于X所以乘的质数必须是X的质因数且总次数等于指数。所以最长链的长度依然是total 1链的数目依然是多重集排列数。结论是在这个问题中“中间项是X的因子”这个条件对于最长链的长度和数量并没有增加额外的约束它只是确保了链上的所有数都在X的因子集合内这个性质。这是一个有趣的发现说明原题的条件设计得非常精巧既增加了题目的趣味性又没有改变最优化问题的数学本质。最后回顾整个解题过程从理解题意、转化问题算术基本定理到设计高效算法获取输入线性筛再到运用组合数学计算答案最后考虑边界和优化这是一道非常经典的、考察综合数论与组合思维的题目。它不要求高深的数学知识但需要对基础概念有深刻的理解和灵活的应用能力。在平时练习时多问几个“为什么”比如“为什么这样是最长”“这个公式是怎么来的”并动手实现、测试边界情况才能真正吃透这类题目在赛场上遇到变体也能游刃有余。