算法竞赛数论基石：整数分解从试除法到Pollard-Rho实战

1. 项目概述从“分解”切入理解算法竞赛的数论基石如果你正在备战类似“国赛”级别的算法竞赛或者对编程解题中的数学问题感到头疼那么“整数分解”这个主题你一定绕不开。它不像动态规划那样有炫酷的状态转移也不如图论算法那样有复杂的结构但它是数论领域最基础、最核心的技能之一是解决大量中高级题目的“前置关卡”。很多题目看似复杂其核心难点最终都会落到对整数性质的深入理解和快速处理上而分解正是打开这扇大门的钥匙。这次我们聚焦于AOJAizu Online Judge这个经典的算法题库平台来一次针对“整数分解”问题的深度集训。AOJ上的题目质量高、分类清晰尤其适合进行专题突破。所谓“分解篇”不仅仅是学会把一个数拆成质因数乘积那么简单。它是一套组合拳涵盖了从最基础的试除法到需要数论定理支撑的Pollard-Rho大数分解再到如何利用分解结果去解决最大公约数(GCD)、最小公倍数(LCM)、因子个数、因子和等一系列衍生问题。掌握它意味着你拥有了将复杂的整数问题“化整为零”的能力这在竞赛中往往是破题的关键一步。2. 核心思路与知识体系构建面对整数分解相关题目不能只停留在“暴力求解”的层面。我们需要建立一个清晰的决策树根据数据规模和时间限制选择最高效的武器。2.1 问题分类与应对策略竞赛中的分解问题大致可以分为三类每一类对应不同的策略单次分解数值较小n ≤ 10^12这是最常见的情况。通常使用预处理素数表 试除法即可。关键在于素数表要开多大一般sqrt(10^12) 10^6所以我们预处理10^6以内的素数就足够了。利用埃拉托斯特尼筛法埃氏筛或欧拉筛线性筛快速得到素数表然后只用素数去试除效率远高于用所有奇数去试。单次分解数值巨大n ≤ 10^18这是进阶挑战。试除法已经力不从心需要用到Miller-Rabin素数测试和Pollard-Rho因数分解算法。Miller-Rabin是一个概率性算法能以极高的正确率快速判断一个大整数是否为素数。Pollard-Rho则是一个巧妙的随机算法用于找出大整数的一个非平凡因子。两者结合构成了分解大整数的标准流程。多次查询或需要分解后的衍生信息题目可能要求频繁查询某个数的因子个数或者多次计算GCD、LCM。这时单纯的分解可能造成重复计算。我们需要引入预处理和数论函数的概念。例如可以用线性筛在O(n)时间内预处理出1到N每个数的最小质因子spf。这样每次分解一个数n时可以不断地除以它的spf在O(log n)时间内完成分解并同步计算出因子个数、因子和等。这对于需要处理大量查询的题目至关重要。2.2 必备数论概念精讲要玩转分解必须吃透以下几个概念它们是你工具箱里的螺丝刀和扳手素数与合数质数是只有1和自身两个正因数的数。1既不是素数也不是合数这是一个非常容易忽略的边界条件必须特别注意。算术基本定理任何一个大于1的自然数N都可以唯一地分解成有限个质数的乘积。即 N p1^a1 * p2^a2 * ... * pk^ak。这个“唯一”是分解问题的理论基石。最大公约数与最小公倍数GCDGreatest Common Divisor通常使用欧几里得算法辗转相除法求解其核心原理是 gcd(a, b) gcd(b, a mod b)。这个算法效率极高复杂度为O(log min(a, b))。LCMLeast Common Multiple可以通过GCD推导lcm(a, b) a / gcd(a, b) * b。注意要先除后乘防止中间结果溢出。同余理解“a ≡ b (mod m)”意味着m整除(a-b)。同余理论是解决许多数论问题的钥匙但在基础的分解问题中它更多是作为Pollard-Rho等算法的背景知识。3. 核心算法解析与C实现理论需要代码来落地。下面我们用C来实现分解问题的核心武器库。3.1 基础装备素数筛与试除法首先我们打造最常用的工具线性筛欧拉筛和基于素数表的试除法。#include vector #include cmath using namespace std; const int MAXN 1000000; // 根据题目数据范围调整 // 线性筛法求1~MAXN的所有素数并记录每个数的最小质因子 vectorint primes; int spf[MAXN 1]; // smallest prime factor void linear_sieve() { for (int i 2; i MAXN; i) { if (spf[i] 0) { // i是素数 spf[i] i; primes.push_back(i); } for (int p : primes) { if (p spf[i] || i * p MAXN) break; spf[i * p] p; } } } // 使用素数表进行试除法分解返回质因数及其指数 vectorpairlong long, int trial_divide(long long n) { vectorpairlong long, int factors; if (n 1) return factors; // 处理边界 long long temp n; // 只用素数试除到 sqrt(n) for (int p : primes) { if ((long long)p * p temp) break; if (temp % p 0) { int cnt 0; while (temp % p 0) { temp / p; cnt; } factors.emplace_back(p, cnt); } } // 循环结束后如果 temp 1说明它本身就是一个大于 sqrt(原n) 的质因数 if (temp 1) { factors.emplace_back(temp, 1); } return factors; }注意trial_divide函数中循环条件是p * p temp而不是固定的p sqrt(n)。因为temp在循环过程中不断减小及时更新上界可以节省大量不必要的计算。这是优化试除法效率的一个关键细节。3.2 进阶武器Miller-Rabin与Pollard-Rho当n大到10^18时我们需要更强大的算法。这里给出一个经过竞赛检验的实现模板。#include cstdlib #include ctime using namespace std; typedef long long ll; typedef __int128 i128; // 使用128位整数防止乘法溢出 // 快速幂取模 (a^b % mod)使用128位中间变量防溢出 ll qpow(i128 a, ll b, ll mod) { i128 res 1; a % mod; while (b) { if (b 1) res (res * a) % mod; a (a * a) % mod; b 1; } return (ll)res; } // Miller-Rabin素数测试确定性版本适用于 2^64 以内 bool is_prime(ll n) { if (n 2) return false; if (n 2 || n 3) return true; if (n % 2 0 || n % 3 0) return false; // 测试的基底对于 2^64 以内足够 ll bases[] {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; ll d n - 1; int s 0; while (d % 2 0) d / 2, s; for (ll a : bases) { if (a % n 0) continue; ll x qpow(a, d, n); if (x 1 || x n - 1) continue; bool composite true; for (int r 1; r s; r) { x (i128)x * x % n; if (x n - 1) { composite false; break; } } if (composite) return false; } return true; } // Pollard-Rho 算法的随机函数 f(x) (x*x c) % n ll f(ll x, ll c, ll n) { return ((i128)x * x c) % n; } // 使用Pollard-Rho算法找出n的一个非平凡因子 ll pollard_rho(ll n) { if (n 4) return 2; // 对4特殊处理 if (is_prime(n)) return n; // 如果是质数直接返回自身 // 随机种子 ll x rand() % (n - 2) 2, y x; ll c rand() % (n - 1) 1; ll d 1; while (d 1) { x f(x, c, n); y f(f(y, c, n), c, n); d __gcd(abs(x - y), n); if (d n) return pollard_rho(n); // 失败重新随机参数 } return d; } // 主分解函数递归使用Pollard-Rho返回所有质因数未排序 void factorize(ll n, vectorll factors) { if (n 2) return; if (is_prime(n)) { factors.push_back(n); return; } ll d pollard_rho(n); factorize(d, factors); factorize(n / d, factors); }实操心得Miller-Rabin算法中的基底选择至关重要。上面代码中使用的7个基底是针对64位整数2^64以内的确定性测试集这意味着只要n在2^64以内这个is_prime函数的结果就是绝对正确的而不是概率性的。这省去了我们处理概率问题的麻烦在竞赛中非常可靠。4. 从分解到应用解决经典问题模式掌握了分解的“术”更要理解其“道”。分解本身不是目的利用分解结果解决问题才是。下面看几个经典模式。4.1 计算因子个数与因子和根据算术基本定理 N p1^a1 * p2^a2 * ... * pk^ak正因子个数num (a1 1) * (a2 1) * ... * (ak 1)正因子和sum (p1^(a11)-1)/(p1-1) * (p2^(a21)-1)/(p2-1) * ... * (pk^(ak1)-1)/(pk-1)// 接在 trial_divide 或 factorize 获得质因数向量 factors 后 long long count_divisors(const vectorpairlong long, int factors) { long long cnt 1; for (auto [p, exp] : factors) { cnt * (exp 1); } return cnt; } long long sum_of_divisors(const vectorpairlong long, int factors) { long long sum 1; for (auto [p, exp] : factors) { // 计算 (p^(exp1) - 1) / (p - 1) long long term 1; long long power 1; for (int i 0; i exp; i) { power * p; } term (power - 1) / (p - 1); sum * term; } return sum; }4.2 解决GCD与LCM相关问题有一类常见问题给定多个数求它们所有因子或满足某些条件的因子的GCD或LCM。这时分解并分析每个质因数的指数是关键。模式设数组为a[1...n]。令每个数分解后质因数p的指数为e_i。对于求所有数共有因子的某种性质如最大公约数本身关注的是每个质因数指数的最小值gcd_exp[p] min(e1, e2, ..., en)。对于求能整除所有数的某种性质如最小公倍数关注的是每个质因数指数的最大值lcm_exp[p] max(e1, e2, ..., en)。例如题目“求一个最小的正整数使得它能整除数组A中所有数且自身是数组B中所有数的倍数”。这其实就是求一个数X满足lcm(A) | X且X | gcd(B)。解题思路就是分别计算lcm_A和gcd_B然后找出所有满足条件的X本质上还是在处理质因数指数的范围[max_A_exp, min_B_exp]。5. AOJ真题实战与调试技巧我们选取AOJAizu Online Judge上几道典型的题目来串联上述知识。5.1 NTL_1_A: Prime Factorization (试除法模板题)题目链接http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?idNTL_1_A题意给定一个整数n (1 n ≤ 10^9)输出其质因数分解式。分析这是最基础的试除法应用。n≤10^9sqrt(n)≈31622我们只需要预处理出35000以内的素数即可。直接使用trial_divide函数然后按格式输出。注意点输出格式要求严格形如n: p1 e1 p2 e2 ...。需要先输出n:并且质因数按升序排列。我们的trial_divide函数中由于素数表本身是升序的所以得到的因数自然有序。5.2 NTL_1_B: Power (模幂运算)题目链接http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?idNTL_1_B题意计算 M^N mod 1000000007。分析虽然这不是直接的分解题但快速幂取模是数论计算中最基本的操作也是Miller-Rabin算法的基础。直接用我们实现的qpow函数即可。注意使用i128防止中间乘法溢出。5.3 经典问题模式枚举因子很多题目需要枚举一个数的所有因子。分解后可以通过DFS递归生成所有因子组合。vectorlong long get_divisors(long long n) { auto factors trial_divide(n); // 或 factorize(n) vectorlong long divisors {1}; for (auto [p, exp] : factors) { int sz divisors.size(); long long mul 1; for (int i 0; i exp; i) { mul * p; for (int j 0; j sz; j) { divisors.push_back(divisors[j] * mul); } } } // 排序如果需要的话 sort(divisors.begin(), divisors.end()); return divisors; }5.4 调试与常见问题排查时间超限TLE试除法检查素数表上界是否足够应≥sqrt(MAX_N)循环条件是否为p*p temp。Pollard-Rho这是一个随机算法存在极低概率陷入死循环d n。代码中通过递归调用pollard_rho(n)来重新随机参数但理论上仍有可能概率极低无限递归。竞赛中通常足够安全。可以设置递归深度上限或尝试固定几组不同的c值。答案错误WA边界条件n0, 1, 负数如果题目允许的处理是否正确1不是素数也不是合数分解结果应为空。溢出这是数论题最大的坑。在计算p^exp、中间乘法、求因子和时非常容易超出long long范围。务必使用__int128GCC/Clang支持或手动实现快速乘来应对。Miller-Rabin基底确保使用的基底集合对于你的数据范围是确定正确的。对于long long2^63-1以内上文提供的7个基底是可靠的。内存超限MLE素数表primes和spf数组的大小需要根据题目要求精确设定不要盲目开大数组。踩坑记录我曾在一道题中因为因子个数计算公式cnt * (exp 1)没有使用long long而导致溢出WA。exp是int但(exp1)相乘后可能很大。另一个常见错误是在计算LCM时写成a * b / gcd(a, b)这会在a*b时溢出。必须写成a / gcd(a, b) * b。这些细节在竞赛中往往是致命的。