1. 题目背景与核心思路解析洛谷P1445这道题乍看是一道普通的数学题但深入分析后发现它巧妙融合了数论中的两个重要工具整数唯一分解定理和欧拉筛。题目要求我们找到满足特定条件的正整数对(x,y)的数量这个条件可以转化为关于n!的因数分解问题。1.1 数学建模过程首先观察题目给出的方程1/x 1/y 1/n!。通过代数变形可以得到(x y)/(xy) 1/n! ⇒ xy n!(x y) ⇒ xy - n!x - n!y 0为了将其转化为更易处理的形式我们可以在等式两边加上(n!)²xy - n!x - n!y (n!)² (n!)² ⇒ (x - n!)(y - n!) (n!)²这个变形是解题的关键转折点。现在问题转化为找到所有正整数对(a,b)使得a × b (n!)²其中a x - n!b y - n!。1.2 因数个数与唯一分解定理根据整数唯一分解定理任何大于1的正整数都可以唯一表示为质数的幂的乘积。对于(n!)²我们可以先对n!进行质因数分解然后平方每个质因数的指数。设n!的质因数分解为n! p₁^a₁ × p₂^a₂ × ... × p_k^a_k那么(n!)²的分解就是p₁^(2a₁) × p₂^(2a₂) × ... × p_k^(2a_k)根据数论知识一个数的因数个数等于其所有质因数指数加1的乘积。因此(n!)²的因数个数为(2a₁ 1)(2a₂ 1)...(2a_k 1)由于题目中的x和y都是正整数且a和b是一一对应的交换a和b得到不同的(x,y)对所以最终的解的个数就是(n!)²的因数个数。2. 质因数分解的实现策略2.1 欧拉筛法预处理质数为了高效计算n!的质因数分解我们需要先得到所有≤n的质数。欧拉筛线性筛是最佳选择因为它能在O(n)时间内筛出所有质数且每个合数只被标记一次。欧拉筛的核心思想是让每个合数只被其最小的质因数筛掉。实现时需要维护一个质数表和一个标记数组const int MAXN 1e6 5; bool is_prime[MAXN]; vectorint primes; void euler_sieve(int n) { memset(is_prime, true, sizeof(is_prime)); is_prime[0] is_prime[1] false; for (int i 2; i n; i) { if (is_prime[i]) primes.push_back(i); for (int j 0; j primes.size() i * primes[j] n; j) { is_prime[i * primes[j]] false; if (i % primes[j] 0) break; } } }2.2 计算n!的质因数分解对于n!的质因数分解Legendre公式给出了高效计算方法对于每个质数p≤n其在n!中的指数为e(p) ⌊n/p⌋ ⌊n/p²⌋ ⌊n/p³⌋ ...这个求和过程直到p^k n时停止。实现代码如下vectorpairint, int factorize_factorial(int n) { vectorpairint, int factors; for (int p : primes) { if (p n) break; int cnt 0, tmp n; while (tmp 0) { tmp / p; cnt tmp; } factors.emplace_back(p, cnt); } return factors; }3. 完整解题流程与代码实现3.1 算法步骤整合使用欧拉筛预处理所有≤n的质数对每个质数p计算其在n!中的指数e(p)计算(2e(p)1)的乘积即为答案注意结果需要取模题目通常要求模一个大质数3.2 完整AC代码#include iostream #include vector #include cstring using namespace std; const int MAXN 1e6 5; const int MOD 1e9 7; bool is_prime[MAXN]; vectorint primes; void euler_sieve(int n) { memset(is_prime, true, sizeof(is_prime)); is_prime[0] is_prime[1] false; for (int i 2; i n; i) { if (is_prime[i]) primes.push_back(i); for (int j 0; j primes.size() i * primes[j] n; j) { is_prime[i * primes[j]] false; if (i % primes[j] 0) break; } } } int main() { int n; cin n; // Step 1: 筛出所有质数 euler_sieve(n); // Step 2: 计算n!的质因数分解 long long ans 1; for (int p : primes) { if (p n) break; int cnt 0, tmp n; while (tmp 0) { tmp / p; cnt tmp; } // Step 3: 计算(2e1)的乘积 ans ans * (2 * cnt 1) % MOD; } cout ans endl; return 0; }4. 性能优化与边界情况4.1 时间复杂度分析欧拉筛O(n)质因数分解对于每个质数p计算指数的复杂度为O(log_p n) 由于质数个数约为n/ln n总复杂度约为O(n)因为∑log_p n ≈ n因此整体算法是线性的对于n≤10^6的数据规模完全可行。4.2 常见错误与调试技巧筛法边界错误确保筛的范围足够大≥n同时数组大小要匹配调试技巧打印出筛得的质数列表验证是否正确整数溢出问题在计算(2e1)乘积时要及时取模经验对于乘法操作每步都取模最安全特殊输入处理n1时结果为1需要单独验证测试用例n1 → 1n2 → 3n3 → 9质数判断错误确保欧拉筛正确标记了所有合数验证方法与简单筛法结果对比5. 数学原理深度解析5.1 唯一分解定理的严谨表述算术基本定理唯一分解定理严格表述为任何大于1的正整数n都可以唯一地表示为n p₁^α₁ × p₂^α₂ × ... × p_k^α_k其中p₁ p₂ ... p_k是质数α_i是正整数。这个唯一性指的是质因数及其指数的排列顺序是唯一的。5.2 因数个数公式的推导对于n p₁^α₁ × p₂^α₂ × ... × p_k^α_k其任意因数d可以表示为d p₁^β₁ × p₂^β₂ × ... × p_k^β_k其中0 ≤ β_i ≤ α_i因此每个β_i有(α_i 1)种选择根据乘法原理总因数个数为τ(n) (α₁ 1)(α₂ 1)...(α_k 1)在本题中(n!)²的每个指数都是偶数所以公式变为(2α₁ 1)(2α₂ 1)...(2α_k 1)5.3 欧拉筛的线性时间证明欧拉筛之所以能达到O(n)复杂度关键在于两点每个合数只被其最小质因数筛除内层循环在i % primes[j] 0时立即break这样保证了每个合数只被标记一次。例如数字6只会被2×3标记不会被3×2标记数字12只会被2×6标记不会继续用3×4标记6. 实际应用与扩展思考6.1 类似题目推荐约数个数问题给定n统计其所有因数的个数约数和问题计算n的所有因数之和GCD配对统计统计数组中满足特定GCD条件的数对6.2 算法扩展应用RSA加密算法依赖大整数的质因数分解困难性离散对数问题在密码学中有重要应用组合数学问题如计算排列组合数的质因数分解6.3 性能优化进阶对于更大的n如n≤10^7可以考虑以下优化分段筛法处理内存限制严格的情况预处理最小质因子加速任意数的分解并行计算利用多线程加速筛法过程在实际编码比赛中这类数学题往往考察选手对数论工具的灵活运用能力。掌握欧拉筛和唯一分解定理的组合应用可以解决一大类因数相关的计数问题。
