线性筛还能这么用？一个‘球与盒子’的数学问题，让我重新理解了因子计数

线性筛还能这么用一个‘球与盒子’的数学问题让我重新理解了因子计数在算法竞赛和数论研究中线性筛Eratosthenes筛法的优化版本常被视为质数筛选的标配工具。但最近遇到的一个组合数学问题彻底颠覆了我对线性筛的认知——它不仅能高效筛选质数还能在解决球与盒子这类看似无关的问题时大显身手。本文将带你从零开始探索线性筛在因子计数问题中的神奇应用。1. 问题背景与核心观察假设有n个盒子和n个球每个盒子必须放入一个球。特殊之处在于盒子编号和放入的球编号必须具有相同数量的因子。例如编号为6的盒子因子为1,2,3,6只能放入因子数同样为4的球。关键观察点因子数相同的编号构成等价类每个等价类内部可以任意排列阶乘关系整体解是各等价类解的组合乘积# 示例n3时的合法排列 盒子编号1(1因子), 2(2因子), 3(2因子) 合法排列 1→1, 2→2, 3→3 1→1, 2→3, 3→2 # 共2种有效排列2!2. 线性筛的传统认知与突破传统线性筛主要用于质数筛选其核心优势是O(n)时间复杂度。标准实现如下vectorbool is_prime(n1, true); vectorint primes; for (int i 2; i n; i) { if (is_prime[i]) primes.push_back(i); for (int p : primes) { if (i*p n) break; is_prime[i*p] false; if (i%p 0) break; } }创新应用通过改造线性筛我们可以同时计算每个数的因子个数。关键在于维护两个数组min_prime记录每个数的最小质因子min_prime_cnt记录最小质因子的次数3. 因子计数的数学原理任何正整数n的质因数分解为 n p₁^k₁ × p₂^k₂ × ... × p_m^k_m因子总数公式 d(n) (k₁1) × (k₂1) × ... × (k_m1)线性筛改造策略遇到质数p时d(p) 2筛合数i×p时若p不整除id(i×p) d(i)×2若p整除i设i p^k×m则d(i×p) d(i)×(k2)/(k1)优化后的筛法实现vectorint d(n1, 1); // 因子个数数组 vectorint min_p(n1, 0), cnt_p(n1, 0); for (int i 2; i n; i) { if (min_p[i] 0) { // i是质数 min_p[i] i; cnt_p[i] 1; d[i] 2; } for (int p : primes) { if (p min_p[i] || i*p n) break; min_p[i*p] p; if (p min_p[i]) { cnt_p[i*p] cnt_p[i] 1; d[i*p] d[i] * (cnt_p[i*p]1) / (cnt_p[i]1); } else { cnt_p[i*p] 1; d[i*p] d[i] * 2; } } }4. 问题求解的完整框架结合线性筛的因子计数能力我们可以构建完整的解决方案预处理阶段使用改造后的线性筛计算1~nmax每个数的因子个数统计每个因子数出现的次数cnt[d]预计算阶乘数组fact[d] cnt[d]!查询处理对于查询n若n ≥ 2250000直接返回0模数性质否则返回∏ fact[d] mod 500009性能对比方法预处理时间查询时间适用场景标准线性筛O(n)O(n)小规模数据优化筛法O(n)O(1)大规模查询数学推导-O(√n)单次查询5. 实际应用中的技巧与陷阱常见误区直接计算每个数的因子数O(n√n)复杂度忽略模数的特殊性质当n≥2250000时答案必为0阶乘计算时未考虑模数限制优化技巧# 利用模数性质提前终止计算 if n 2250000: return 0 # 动态维护结果 res 1 cnt defaultdict(int) for i in range(1, n1): d num_divisors[i] cnt[d] 1 res res * cnt[d] % MOD if res 0: break6. 思维拓展与应用场景这种基于线性筛的因子计数方法还可应用于完全数查找σ(n)2n亲和数判定σ(a)σ(b)ab高度合数筛选因子数超过所有更小的数在最近的一次编程竞赛中我就遇到了一个需要快速统计区间内因子数分布的问题。当时直接套用这个改造后的线性筛不仅正确解出了题目还因为算法效率获得了性能最优奖。