【题目来源】
【题目描述】
求方程 1/x+1/y=1/n! 的正整数解的组数，答案对 10^9+7 取模。
【输入格式】
输入只有一行一个整数，表示 n。
【输出格式】
输出一行一个整数表示正整数解的组数模 10^9+7 的值。
【输入样例一】
2
【输出样例一】
3
【输入样例二】
1439
【输出样例二】
102426508
【数据范围】
对于 30% 的数据，保证 n≤100。
对于 100% 的数据，保证 1≤n≤10^6。
【算法分析】
● 整数唯一分解定理（算术基本定理）
任何一个大于 1 的正整数 n，都可以唯一地表示成有限个质数的乘积形式：n=p₁ᵏ¹×p₂ᵏ²×...×pₘᵏᵐ，其中 p₁<p₂<...<pₘ 是质数，k₁，k₂，....，kₘ 是正整数.且这种分解方式在不考虑顺序的情况下是唯一的。
● 整数唯一分解定理是欧拉函数计算公式的理论基础，欧拉函数是整数唯一分解定理的重要应用之一。通俗地讲，整数唯一分解定理是 “地基”，欧拉函数公式是 “盖在地基上的房子”；没有地基，房子建不起来；房子的存在，也印证了地基的稳固。
欧拉函数性质 →
欧拉函数 φ(n) 是数论中的重要函数，用于计算 1~n 中与 n 互质的正整数的个数。特别地，当 n=1 时，φ(1)=1。
（1）若 p 是质数，φ(p)=p-1。
例如，φ(5)=5-1=4（表示 1~5 中与 5 互质的正整数有 1,2,3,4 等 4 个）。
（2）若 n=pᵏ，φ(pᵏ)=pᵏ-pᵏ⁻¹。
例如，φ(8)=2³-2²=8-4=4（表示 1~8 中与 8 互质的正整数有 1,3,5,7 等 4 个）
（3）积性函数：当 a,b 互质时，φ(ab)=φ(a)φ(b)。
例如，φ(10)=φ(2)×φ(5)=1×4=4（表示 1~10 中与 10 互质的正整数有 1,3,7,9 等 4 个）
（4）通用计算公式：φ(n)=n×(1-1/p₁)×(1-1/p₂)×...×(1-1/pₘ)。其中，p₁，…，pₘ，是 n 的所有质因数。
例如， 由于 18=2×3²，所以 φ(18)=18×(1-1/2)×(1-1/3)=6（表示 1~18 中与 18 互质的正整数有 1,5,7,11,13,17 等 6 个）。
● 欧拉筛简介：
欧拉筛（Euler Sieve / Linear Sieve）是一种线性时间复杂度（O(n)）的素数筛选算法，核心目标是找出 2~n 范围内的所有素数，且保证每个合数只被它的最小质因子筛除一次 —— 这是它区别于其他筛法（如埃氏筛）的关键，也是 “线性复杂度” 的来源。
但是要注意，欧拉筛不是欧拉发明的。之所以叫欧拉筛，原因在于欧拉筛的核心思想用到了整数唯一分解定理（任何一个大于 1 的整数 N，都可以唯一地表示成若干个质数的乘积）。而欧拉对此贡献巨大，所以后人把这种线性筛尊称为：欧拉筛（Euler sieve）。欧拉筛的核心代码如下所示。
void euler_sieve(int n) {st.assign(n+1,true); //0~nst[0]=st[1]=false;for(int i=2; i<=n; i++) {if(st[i]) p.push_back(i);for(int j=0; (LL)p[j]*i<=n; j++) {st[p[j]*i]=false;if(i%p[j]==0) break;}}
}
欧拉筛（线性筛） 通过每个合数仅被其最小质因数筛除的规则，将时间复杂度优化至严格 O(n)，使得欧拉筛是处理更大范围素数（如 1e7~1e8）的优选算法。
● 本题（洛谷 P1445）的解题思路
步骤 1：方程变形推导核心结论
对原方程 1/x + 1/y = 1/n! 进行变形：
通分得：y + x = xy/(n!) → xy - n!x - n!y = 0
两边加 (n!)² 配方：(x - n!)(y - n!) = (n!)²
因此，方程的正整数解组数等价于 (n!)² 的正约数个数（每一个约数 d 对应一组解：x = n! + d，y = n! + (n!)²/d）。
步骤 2：约数个数定理
若一个数的质因数分解为 m = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ，则 m 的正约数个数为 (a₁+1)×(a₂+1)×...×(aₖ+1)。
对于 (n!)²，其质因数分解为 p₁^(2×b₁) × p₂^(2×b₂) × ... × pₖ^(2×bₖ)（其中 bᵢ 是 n! 中 pᵢ 的指数），因此约数个数为 (2×b₁+1)×(2×b₂+1)×...×(2×bₖ+1)。
步骤 3：计算 n! 的质因数指数
对每个质数 p≤n，计算 p 在 n! 中的指数：b = floor(n/p) + floor(n/p²) + floor(n/p³) + ...（直到 pᵏ > n）。
步骤 4：预处理 + 模运算
用欧拉筛预处理 1~n 的质数
对每个质数计算指数，再计算 (2*b+1) 的乘积（模 1e9+7）
【算法代码】
#include<bits/stdc++.h>
using namespace std;typedef long long LL;
const int MOD=1e9+7;
vector<bool> st; //isPrime
vector<int> p; //primevoid euler_sieve(int n) {st.assign(n+1,true); //0~nst[0]=st[1]=false;for(int i=2; i<=n; i++) {if(st[i]) p.push_back(i);for(int j=0; (LL)p[j]*i<=n; j++) {st[p[j]*i]=false;if(i%p[j]==0) break;}}
}//Calculate the exponent of prime number x in n!
LL get_exponent(int n,int x) {LL exp=0;while(n) {n/=x;exp+=n;}return exp;
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin>>n;euler_sieve(n);LL ans=1;for(int x:p) {LL exp=get_exponent(n,x);ans=ans*(2*exp+1)%MOD;}cout<<ans<<endl;return 0;
}/*
in:1439
out:102426508
*/
【参考文献】