CSP 202312-2 因子化简3种质因数分解算法对比与10^10边界优化在算法竞赛和编程认证考试中质因数分解是一个经典且高频出现的问题。CCF CSP认证2023年12月的第二题因子化简就考察了这一核心算法能力。本文将深入探讨三种主流质因数分解算法在10^10数据规模下的性能表现并提供针对大数优化的实用技巧。1. 问题重述与核心挑战给定正整数n和阈值k要求将n分解为质因数的乘积形式去除所有指数小于k的质因子返回剩余质因子的乘积。例如输入n2155895064k3分解得n2³×3²×23⁴×107¹去除指数小于3的项3²和107¹输出2³×23⁴2238728关键约束条件1 n ≤ 10^101 k, q ≤ 10q为查询次数这个问题的核心挑战在于如何在有限时间内高效完成大数的质因数分解。对于n10^10的情况简单的试除法可能需要执行√n≈10^5次循环在多个查询时可能面临性能瓶颈。2. 三种质因数分解算法对比2.1 基础试除法最直观的分解方法从2开始逐个尝试除数def trial_division(n): factors {} while n % 2 0: factors[2] factors.get(2, 0) 1 n n // 2 i 3 while i * i n: while n % i 0: factors[i] factors.get(i, 0) 1 n n // i i 2 if n 1: factors[n] 1 return factors时间复杂度O(√n)优点实现简单不需要预处理缺点对大数效率较低重复测试合数2.2 预处理素数筛法先用埃拉托斯特尼筛法预处理素数表再用这些素数进行分解def sieve(limit): sieve [True] * (limit 1) sieve[0] sieve[1] False for i in range(2, int(limit**0.5) 1): if sieve[i]: sieve[i*i::i] [False] * len(sieve[i*i::i]) return [i for i, is_prime in enumerate(sieve) if is_prime] def prime_sieve_factorization(n, primes): factors {} for p in primes: if p * p n: break while n % p 0: factors[p] factors.get(p, 0) 1 n n // p if n 1: factors[n] 1 return factors时间复杂度筛法预处理O(n log log n)单次查询O(π(√n))≈O(√n / ln n)优点多次查询时效率高避免测试合数缺点预处理需要额外空间对大数仍需较大素数表2.3 Pollards Rho算法基于随机算法的快速分解方法import random import math def pollards_rho(n): if n % 2 0: return 2 if n % 3 0: return 3 if n % 5 0: return 5 while True: c random.randint(1, n-1) f lambda x: (pow(x, 2, n) c) % n x, y, d 2, 2, 1 while d 1: x f(x) y f(f(y)) d math.gcd(abs(x - y), n) if d ! n: return d def factor(n): factors [] def _factor(n): if n 1: return if is_prime(n): factors.append(n) return d pollards_rho(n) _factor(d) _factor(n // d) _factor(n) return factors时间复杂度期望时间O(n^(1/4))优点对大数效率极高适合单次大数分解缺点实现复杂有概率性因素3. 性能对比与适用场景我们通过实验对比三种算法在n10^10边界下的表现算法类型预处理时间单次查询时间内存占用适用场景试除法无约10^5次操作O(1)简单问题少量查询素数筛法O(n loglogn)≈10^4次操作O(√n)多次查询内存充足Pollards Rho无≈10^3次操作O(1)大数分解单次查询注意实际选择算法时还需考虑编程语言的执行效率。在C中试除法可能已经足够快而Python等解释型语言可能需要更高效的算法。4. 关键优化技巧针对10^10数据规模的优化策略4.1 提前终止循环在试除法和筛法中当n被分解到1时立即终止while i * i n and n 1: # 添加n1条件 # 分解逻辑4.2 只检查奇数除2外其他偶数不可能是质因数# 先处理2 while n % 2 0: # ... # 然后从3开始步长为2 i 3 while i * i n: # ... i 24.3 预处理小素数结合筛法和试除法的优点预处理√n范围内的小素数vectorint primes sieve(1e5); // 预处理10^5以内的素数 void factorize(long long n, mapint,int factors) { for (int p : primes) { if (p*p n) break; while (n % p 0) { factors[p]; n / p; } } if (n 1) factors[n]; }4.4 记忆化存储对于多查询场景缓存已分解的数factor_cache {} def cached_factor(n): if n in factor_cache: return factor_cache[n].copy() factors factor(n) factor_cache[n] factors.copy() return factors5. 完整实现与测试综合以上优化给出C实现示例#include iostream #include vector #include unordered_map using namespace std; vectorint sieve(int limit) { vectorbool is_prime(limit 1, true); vectorint primes; for (int i 2; i limit; i) { if (is_prime[i]) { primes.push_back(i); for (int j i * i; j limit; j i) { is_prime[j] false; } } } return primes; } long long factorize(long long n, int k, const vectorint primes) { long long result 1; for (int p : primes) { if (p * p n) break; if (n % p 0) { int cnt 0; while (n % p 0) { n / p; cnt; } if (cnt k) { for (int i 0; i cnt; i) { result * p; } } } } if (n 1 k 1) { result * n; } return result; } int main() { const int PRE_LIMIT 1e5; vectorint primes sieve(PRE_LIMIT); int q; cin q; while (q--) { long long n; int k; cin n k; cout factorize(n, k, primes) endl; } return 0; }测试用例分析小质数乘积n2×3×530, k1 → 30大质数平方n9973²99460729, k2 → 99460729边界值n9999999999(最大输入), k1 → 需要快速分解6. 算法选择建议根据实际场景选择最合适的算法CSP考试场景时间紧迫建议使用优化后的试除法预处理小素数可以提升速度但非必需注意使用long long类型防止溢出竞赛场景提前准备Pollards Rho模板应对大数分解多查询时考虑筛法预处理工程应用结合多种算法根据输入规模动态选择考虑概率算法与确定性算法的平衡在实际编码时还需要注意输入输出效率使用快速IO避免不必要的计算合理使用数据结构存储中间结果质因数分解作为数论基础操作其优化技巧可以推广到许多类似问题。理解这些算法的核心思想比单纯记忆模板更为重要。
CSP 202312-2 因子化简：3种质因数分解算法对比与10^10边界优化
CSP 202312-2 因子化简3种质因数分解算法对比与10^10边界优化在算法竞赛和编程认证考试中质因数分解是一个经典且高频出现的问题。CCF CSP认证2023年12月的第二题因子化简就考察了这一核心算法能力。本文将深入探讨三种主流质因数分解算法在10^10数据规模下的性能表现并提供针对大数优化的实用技巧。1. 问题重述与核心挑战给定正整数n和阈值k要求将n分解为质因数的乘积形式去除所有指数小于k的质因子返回剩余质因子的乘积。例如输入n2155895064k3分解得n2³×3²×23⁴×107¹去除指数小于3的项3²和107¹输出2³×23⁴2238728关键约束条件1 n ≤ 10^101 k, q ≤ 10q为查询次数这个问题的核心挑战在于如何在有限时间内高效完成大数的质因数分解。对于n10^10的情况简单的试除法可能需要执行√n≈10^5次循环在多个查询时可能面临性能瓶颈。2. 三种质因数分解算法对比2.1 基础试除法最直观的分解方法从2开始逐个尝试除数def trial_division(n): factors {} while n % 2 0: factors[2] factors.get(2, 0) 1 n n // 2 i 3 while i * i n: while n % i 0: factors[i] factors.get(i, 0) 1 n n // i i 2 if n 1: factors[n] 1 return factors时间复杂度O(√n)优点实现简单不需要预处理缺点对大数效率较低重复测试合数2.2 预处理素数筛法先用埃拉托斯特尼筛法预处理素数表再用这些素数进行分解def sieve(limit): sieve [True] * (limit 1) sieve[0] sieve[1] False for i in range(2, int(limit**0.5) 1): if sieve[i]: sieve[i*i::i] [False] * len(sieve[i*i::i]) return [i for i, is_prime in enumerate(sieve) if is_prime] def prime_sieve_factorization(n, primes): factors {} for p in primes: if p * p n: break while n % p 0: factors[p] factors.get(p, 0) 1 n n // p if n 1: factors[n] 1 return factors时间复杂度筛法预处理O(n log log n)单次查询O(π(√n))≈O(√n / ln n)优点多次查询时效率高避免测试合数缺点预处理需要额外空间对大数仍需较大素数表2.3 Pollards Rho算法基于随机算法的快速分解方法import random import math def pollards_rho(n): if n % 2 0: return 2 if n % 3 0: return 3 if n % 5 0: return 5 while True: c random.randint(1, n-1) f lambda x: (pow(x, 2, n) c) % n x, y, d 2, 2, 1 while d 1: x f(x) y f(f(y)) d math.gcd(abs(x - y), n) if d ! n: return d def factor(n): factors [] def _factor(n): if n 1: return if is_prime(n): factors.append(n) return d pollards_rho(n) _factor(d) _factor(n // d) _factor(n) return factors时间复杂度期望时间O(n^(1/4))优点对大数效率极高适合单次大数分解缺点实现复杂有概率性因素3. 性能对比与适用场景我们通过实验对比三种算法在n10^10边界下的表现算法类型预处理时间单次查询时间内存占用适用场景试除法无约10^5次操作O(1)简单问题少量查询素数筛法O(n loglogn)≈10^4次操作O(√n)多次查询内存充足Pollards Rho无≈10^3次操作O(1)大数分解单次查询注意实际选择算法时还需考虑编程语言的执行效率。在C中试除法可能已经足够快而Python等解释型语言可能需要更高效的算法。4. 关键优化技巧针对10^10数据规模的优化策略4.1 提前终止循环在试除法和筛法中当n被分解到1时立即终止while i * i n and n 1: # 添加n1条件 # 分解逻辑4.2 只检查奇数除2外其他偶数不可能是质因数# 先处理2 while n % 2 0: # ... # 然后从3开始步长为2 i 3 while i * i n: # ... i 24.3 预处理小素数结合筛法和试除法的优点预处理√n范围内的小素数vectorint primes sieve(1e5); // 预处理10^5以内的素数 void factorize(long long n, mapint,int factors) { for (int p : primes) { if (p*p n) break; while (n % p 0) { factors[p]; n / p; } } if (n 1) factors[n]; }4.4 记忆化存储对于多查询场景缓存已分解的数factor_cache {} def cached_factor(n): if n in factor_cache: return factor_cache[n].copy() factors factor(n) factor_cache[n] factors.copy() return factors5. 完整实现与测试综合以上优化给出C实现示例#include iostream #include vector #include unordered_map using namespace std; vectorint sieve(int limit) { vectorbool is_prime(limit 1, true); vectorint primes; for (int i 2; i limit; i) { if (is_prime[i]) { primes.push_back(i); for (int j i * i; j limit; j i) { is_prime[j] false; } } } return primes; } long long factorize(long long n, int k, const vectorint primes) { long long result 1; for (int p : primes) { if (p * p n) break; if (n % p 0) { int cnt 0; while (n % p 0) { n / p; cnt; } if (cnt k) { for (int i 0; i cnt; i) { result * p; } } } } if (n 1 k 1) { result * n; } return result; } int main() { const int PRE_LIMIT 1e5; vectorint primes sieve(PRE_LIMIT); int q; cin q; while (q--) { long long n; int k; cin n k; cout factorize(n, k, primes) endl; } return 0; }测试用例分析小质数乘积n2×3×530, k1 → 30大质数平方n9973²99460729, k2 → 99460729边界值n9999999999(最大输入), k1 → 需要快速分解6. 算法选择建议根据实际场景选择最合适的算法CSP考试场景时间紧迫建议使用优化后的试除法预处理小素数可以提升速度但非必需注意使用long long类型防止溢出竞赛场景提前准备Pollards Rho模板应对大数分解多查询时考虑筛法预处理工程应用结合多种算法根据输入规模动态选择考虑概率算法与确定性算法的平衡在实际编码时还需要注意输入输出效率使用快速IO避免不必要的计算合理使用数据结构存储中间结果质因数分解作为数论基础操作其优化技巧可以推广到许多类似问题。理解这些算法的核心思想比单纯记忆模板更为重要。
