算法竞赛整数分解：从试除法到Pollard‘s Rho的实战指南

1. 项目概述从“分解”入手攻克算法竞赛数论基石如果你正在备战蓝桥杯、ICPC这类算法竞赛或者对“国赛”级别的题目感到头疼那么“整数分解”这个主题你一定绕不开。我见过太多队伍卡在看似简单的数论题上根源往往就是对整数性质的理解不够透彻分解质因数的工具用得不熟。这次我们聚焦“AOJ-分解篇”。AOJ作为一个经典的在线评测平台其题目库是许多选手的练兵场。所谓“分解篇”核心就是围绕整数的质因数分解展开的一系列问题它考察的是选手将复杂问题转化为对整数基本构件质数进行操作的能力。这不仅仅是会写一个for循环试除那么简单。在竞赛中你需要面对高达10^18的大整数需要在1秒内完成分解需要利用分解的结果求因数个数、因数之和、欧拉函数值甚至解决模方程、原根等问题。掌握它意味着你掌握了数论武器库中的一把万能钥匙。无论是为了在国赛集训中脱颖而出还是为了夯实自己的算法基础深入理解并熟练运用整数分解技术都是至关重要的一步。接下来我将结合多年刷题和带训的经验为你拆解其中的核心思想、高效算法、经典题型以及那些容易踩坑的细节。2. 核心思路与工具选型为什么“试除法”远远不够当我们拿到一个整数N要求其质因数分解时初学者最直观的想法就是“试除法”从2开始逐个尝试能否整除N。这个思路完全正确但它就像一把小刀处理水果游刃有余面对大树就力不从心了。在算法竞赛中我们必须根据数据规模选择不同的“刀具”。2.1 算法工具箱的层次化选择选择哪种分解算法首要判断依据是数字N的大小范围。以下是竞赛中的常见选择策略小范围试除法 (N ≤ 10^12)原理遍历i从2到sqrt(N)如果N % i 0则i是一个质因子循环除尽它。优化1每次找到因子i后将N不断除以i直到不能整除这样后续的i就只需要检查是否是质数即可因为合数因子已经被之前的质因子除掉了。优化2单独处理偶因子2然后i从3开始每次加2只检查奇数。优化3i的遍历上限是动态的sqrt(N)因为每当N被i除后N和sqrt(N)都会变小。时间复杂度O(sqrt(N))在10^12量级时sqrt(N) 10^6循环百万次在1秒内是可以接受的。// 试除法分解质因数返回质因子及其指数 vectorpairlong long, int factorize(long long n) { vectorpairlong long, int factors; // 处理因子2 if (n % 2 0) { int cnt 0; while (n % 2 0) n / 2, cnt; factors.emplace_back(2, cnt); } // 检查奇数因子 for (long long i 3; i * i n; i 2) { if (n % i 0) { int cnt 0; while (n % i 0) n / i, cnt; factors.emplace_back(i, cnt); } } // 如果最后剩下的n大于1它本身就是一个质数 if (n 1) factors.emplace_back(n, 1); return factors; }Pollards Rho 算法 (N ≤ 10^18)应用场景当N超过10^12试除法不再可行。Pollards Rho是一种概率性算法但对于竞赛中的合数非常高效。核心思想利用生日悖论和Floyd判环算法找到一个非平凡的因子。它基于一个事实如果p是N的一个因子那么函数f(x) (x*x c) % N在模p意义下会产生循环。需要搭配Miller-Rabin 素性测试。在尝试分解前先用Miller-Rabin判断N是否是质数如果是则直接返回如果不是再用Pollards Rho寻找因子。时间复杂度期望O(N^(1/4))对于10^18的数期望运算次数在万级别完全满足时限。注意实现Pollards Rho时需要注意乘法溢出10^18相乘会溢出64位整数需要使用“快速乘”或__int128类型。这是第一个大坑。预处理素数表 试除法 (N 很大但最大质因子较小)场景题目可能暗示或通过分析可知N的质因子不会很大例如所有因子都小于10^6。做法先用欧拉筛预处理出10^6以内的所有质数存放在数组primes中。然后只用这些质数去试除N。优势比普通的奇数试除更快因为跳过了合数的检查。关键点预处理素数表的时间是O(MAXN)空间也是O(MAXN)需要权衡。2.2 为什么这是竞赛的常客整数分解之所以重要是因为它是连接整数与其它数论问题的桥梁。一旦得到质因数分解形式N p1^a1 * p2^a2 * ... * pk^ak许多问题就变成了简单的公式计算因数个数d(N) (a11)*(a21)*...*(ak1)因数之和σ(N) (1p1...p1^a1) * ... * (1pk...pk^ak)欧拉函数φ(N) N * (1 - 1/p1) * ... * (1 - 1/pk)模运算相关求乘法逆元、判断原根、解高次同余方程等都需要对模数m进行分解。因此在竞赛中题目很少直接问“请分解这个数”而是将分解作为解决最终问题的一个必要步骤。你的代码模块里一个健壮的、能够处理大整数的factorize函数是数论题的底气所在。3. 核心算法实现细节与避坑指南理解了选型策略我们来深入两个最关键算法的实现细节这里充满了“教科书不会讲”的实战经验。3.1 Miller-Rabin 素性测试如何可靠地判断大素数在分解一个大整数前我们必须先判断它是不是质数。对于10^18以内的数Miller-Rabin 测试是确定性的使用一组特定的底数。算法原理简化版 基于费马小定理和二次探测定理。对于一个待测奇数n写成n-1 2^s * d的形式。然后选择一个底数a检查以下两个条件是否至少有一个成立a^d ≡ 1 (mod n)存在某个r在[0, s-1)范围内使得a^(2^r * d) ≡ -1 (mod n)如果对于所有选定的底数a条件都满足那么n很可能是素数。实现关键与避坑using ll long long; ll qpow(ll a, ll b, ll mod) { /* 快速幂取模 */ } // Miller-Rabin 检测对于 long long 范围内使用以下一组底数足够确定 bool is_prime(ll n) { if (n 3) return n 2; if (n % 2 0) return false; ll d n - 1, s 0; while (d % 2 0) d / 2, s; // 测试底数集对于 long long 范围这组数足够 vectorll test_a {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; for (ll a : test_a) { if (a % n 0) continue; ll x qpow(a, d, n); if (x 1 || x n - 1) continue; bool ok false; for (int j 0; j s; j) { x (__int128)x * x % n; // 注意使用__int128防溢出 if (x n - 1) { ok true; break; } } if (!ok) return false; } return true; }避坑点1乘法溢出。计算a^d mod n时a和d都可能很大直接乘会溢出long long。必须使用__int128中间类型GCC/Clang支持或手写“快速乘”函数。避坑点2底数选择。对于不同的n的范围有经过验证的确定性底数集合。上面代码中的集合适用于2^64以内。如果环境不支持__int128需要实现快速乘复杂度会多一个 log。3.2 Pollards Rho 算法实战寻找那个“非平凡因子”当is_prime(n)返回false时我们就需要pollard_rho来拆开它。算法步骤如果n是偶数返回因子2。随机生成初始值c和x。定义函数f(x) (x*x c) % n。令y x初始化d 1。当d 1时循环x f(x)y f(f(y))// y跑得快d gcd(abs(x - y), n)如果d n说明本轮没找到换一个c重试。否则d就是n的一个非平凡因子。完整实现与注释ll pollard_rho(ll n) { if (n % 2 0) return 2; if (n % 3 0) return 3; // 随机数生成器 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distributionll dist(1, n-1); ll x dist(rng), y x, c dist(rng); ll d 1; auto f [](ll x) { return ((__int128)x * x c) % n; }; while (d 1) { x f(x); y f(f(y)); d __gcd(abs(x - y), n); if (d n) return pollard_rho(n); // 失败递归重试 } return d; } // 分解主函数递归分解 void factor(ll n, mapll, int factors) { if (n 1) return; if (is_prime(n)) { factors[n]; return; } ll d pollard_rho(n); factor(d, factors); factor(n / d, factors); }避坑点3abs的溢出。x-y可能为负数取绝对值时如果直接abs(x-y)对于long long的极小值LLONG_MIN取绝对值会溢出。安全的做法是ll diff x y ? x - y : y - x;。避坑点4递归深度与栈溢出。虽然Pollards Rho期望很快但最坏情况如n是质数的平方可能导致递归层数较深。在竞赛中n ≤ 10^18通常没问题。如果担心可以改为迭代或显式栈。避坑点5随机种子。使用time(0)在多次调用中可能不够“随机”推荐使用chrono库的高精度时间戳作为种子效果更好。4. 经典题型拆解与实战应用掌握了核武器我们来看看在AOJ或类似题库中“分解”会以怎样的面目出现。我将其归纳为四大类题型。4.1 题型一直接计算与因子相关属性这是最直接的考察。给定N求其因数个数、因数之和、欧拉函数值等。例题模型给定N求φ(N)欧拉函数。解法对N进行质因数分解。代入公式φ(N) N * Π(1 - 1/pi)。计算时为了避免浮点数通常先除再乘ans N; for(auto [p, c] : factors) ans ans / p * (p-1);关键技巧注意N可能很大在乘法时用__int128或取模如果题目要求。如果题目要求的是1..N中所有数的欧拉函数和那就需要用欧拉筛线性预处理而不是对每个数分解。4.2 题型二基于因子结构的计数问题这类问题需要你利用因子的结构进行计数或枚举。例题模型有多少个正整数x满足x是N的因子并且x和N/x互质解法分解N p1^a1 * p2^a2 * ... * pk^ak。对于每个质因子pi它在x和N/x中不能同时出现。也就是说对于每个pi要么它的所有ai次幂都在x中要么都在N/x中。因此每个质因子有2种选择。总方案数就是2^k其中k是不同质因子的个数。核心思维转换将“因子”和“互质”的条件转化为对每个质因子幂次分配的讨论。这是解决此类组合数论问题的通用钥匙。4.3 题型三解模方程与离散对数这是分解问题的高阶应用。例如求解方程a^x ≡ b (mod m)。解法步骤首先分解模数m。如果gcd(a, m) 1可以使用BSGS算法。如果gcd(a, m) 1则需要更复杂的扩展BSGS算法其关键步骤之一就是不断地从方程两边和模数中约去gcd(a, m)直到互质。这个过程需要用到分解得到的质因子信息来判断何时停止。实战要点在实现扩展BSGS时你需要一个高效的gcd和取模运算。分解m虽然可能不是性能瓶颈但清晰的质因子列表有助于你理解算法每一步在做什么方便调试。4.4 题型四大整数分解本身即为答案有些题目就是赤裸裸地要求输出一个超大整数的质因数分解结果。这纯粹是对你实现的Miller-Rabin和Pollards Rho的稳定性和效率的测试。应对策略确保你的随机函数足够随机。使用__int128避免溢出。在递归分解时可以先判断n是否是质数的幂例如检查n的k次根是否为整数且是质数这是一个有效的剪枝。对于非常大的n比如超过10^18可能需要更复杂的算法如二次筛但竞赛中极少见。5. 竞赛中的优化策略与代码模板在紧张的比赛环境中你需要的不仅是一个正确的算法更是一个封装良好、使用顺手、边界清晰的代码模板。5.1 完整数论分解模板C下面是我在比赛中常用的一个整合模板包含了Miller-Rabin、Pollards Rho、质因数分解以及欧拉函数计算。#include bits/stdc.h using namespace std; using ll long long; // ---------- 随机数工具 ---------- mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll rand(ll l, ll r) { return uniform_int_distributionll(l, r)(rng); } // ---------- 快速乘与快速幂 (防溢出) ---------- ll mul(ll a, ll b, ll mod) { return (__int128)a * b % mod; } ll qpow(ll a, ll b, ll mod) { ll res 1; while (b) { if (b 1) res mul(res, a, mod); a mul(a, a, mod); b 1; } return res; } // ---------- Miller-Rabin ---------- bool is_prime(ll n) { if (n 3 || n % 2 0) return n 2; ll d n - 1, s 0; while (d % 2 0) d / 2, s; // 测试基: 2, 325, 9375, 28178, 450775, 9780504, 1795265022 vectorll bases {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; for (ll a : bases) { if (a % n 0) continue; ll x qpow(a, d, n); if (x 1 || x n - 1) continue; bool ok false; for (int j 0; j s; j) { x mul(x, x, n); if (x n - 1) { ok true; break; } } if (!ok) return false; } return true; } // ---------- Pollards Rho ---------- ll pollard_rho(ll n) { if (n % 2 0) return 2; if (n % 3 0) return 3; ll x rand(1, n-1), y x, c rand(1, n-1); ll d 1; auto f [](ll x) { return (mul(x, x, n) c) % n; }; while (d 1) { x f(x); y f(f(y)); d __gcd(abs(x - y), n); if (d n) return pollard_rho(n); } return d; } // ---------- 分解并存储结果 ---------- mapll, int factors; // 全局变量存储质因子及其指数 void factor(ll n) { if (n 1) return; if (is_prime(n)) { factors[n]; return; } ll d pollard_rho(n); factor(d); factor(n / d); } // ---------- 应用示例求欧拉函数 ---------- ll euler_phi(ll n) { factors.clear(); factor(n); ll ans n; for (auto [p, cnt] : factors) { ans ans / p * (p - 1); } return ans; } int main() { ll n; while (cin n n) { cout euler_phi(n) endl; } return 0; }5.2 何时选择更简单的算法模板虽好但杀鸡勿用牛刀。在比赛中养成先分析数据范围的习惯。如果题目保证N ≤ 10^12果断用优化试除法代码更短更不易出错。如果题目说N ≤ 10^18且可能是合数再搬出 Pollards Rho。如果题目需要频繁查询某个值域内所有数的因子属性如1e7以内那么预处理素数表试除或者直接线性筛出每个数的最小质因子是更优的选择。线性筛后分解一个数n的复杂度就降为O(log n)。// 线性筛求每个数的最小质因子 minp const int MAXN 1e7; int minp[MAXN 1]; vectorint primes; void init() { for (int i 2; i MAXN; i) { if (!minp[i]) { minp[i] i; primes.push_back(i); } for (int p : primes) { if (p minp[i] || i * p MAXN) break; minp[i * p] p; } } } // 利用 minp 快速分解 vectorpairint, int factorize_fast(int n) { vectorpairint, int res; while (n 1) { int p minp[n], cnt 0; while (n % p 0) n / p, cnt; res.emplace_back(p, cnt); } return res; }6. 常见“坑点”与调试心得即使算法原理都懂实现起来依然可能漏洞百出。下面是我和队员们踩过的一些典型坑位。坑点11和0的处理。分解质因数时1没有质因子。你的函数在n1时应返回空结果。欧拉函数φ(1)1。这些边界情况在样例中可能不体现但一旦遇到就是WA。坑点2负数的输入。题目通常输入正整数但有时也不保证。如果你的分解函数没有对负数或0做检查可能会陷入死循环比如求绝对值后Pollards Rho中的随机函数范围错误。坑点3乘法溢出无处不在。这是大数运算的头号敌人。不仅在快速幂、快速乘中在计算i*i n这种循环条件时如果i是int而n是long longi*i可能会溢出。安全的写法是i n / i。坑点4递归分解的栈溢出。如前所述对于某些特殊的合数如一个大质数的平方Pollards Rho可能效率较低递归层数加深。在本地测试时可以尝试用ulimit -s unlimited扩大栈空间或者将递归改为用栈模拟。坑点5随机性的质量。不要用rand()它在范围和大数下质量很差。使用 C11 的random库。并且在多次调用时确保随机数生成器不会重复初始化成相同状态。调试心得从小开始先用一些小合数如1000000007 * 1000000009测试你的 Pollards Rho确保它能正确分解。对拍写一个暴力试除法的版本仅用于小数据和你的优化算法对拍随机生成10^12以内的数进行测试。输出中间结果在分解函数里可以临时打印出每次递归调用得到的因子d和剩余的n观察分解过程是否符合预期。关注时间对于10^18的随机合数分解应该在毫秒级完成。如果某个数卡了很久可能是遇到了“强伪素数”或算法实现有误。整数分解是数论的基础也是竞赛中区分度很高的一个考点。它要求你将深刻的数学原理费马小定理、生日悖论转化为高效稳定的代码。通过这个“AOJ-分解篇”的专题训练你真正要掌握的不是几个模板函数而是这种根据问题规模选择工具、深入理解算法细节、严谨处理边界条件的解题思维。当你再看到一道数论题时能下意识地去想“需不需要分解数据范围多大用什么方法分解分解后能直接套用哪个公式”——这时你就真正吃透这个专题了。在国赛级别的比赛中这种扎实的基本功往往就是稳定发挥、避免卡题的保障。