1/N! = 1/X + 1/Y（0<x<=y），给出N，求满足条件的整数解的数量。例如：N = 2，1/2 = 1/3 + 1/6，1/2 = 1/4 + 1/4。由于数量可能很大，输出Mod 10^9 + 7。
输入
输入一个数N（1 <= N <= 1000000)。
输出
输出解的数量Mod 10^9 + 7。
输入样例
2
输出样例
2
1/N! = 1/X + 1/Y
=> 1/N! = (X+Y)/XY
=> XY = N!(X+Y)
=> (X-N!)(Y-N!) = (N!)^2
A*B = (N!)^2
#include <bits/stdc++.h> using namespace std; const int maxn = 2000005; typedef long long ll; const int mod = 1e9 + 7; int prime[maxn]; int isprime[maxn]; int cnt = 0; ll base = 500000004; void getPrime(int n) { isprime[1] = 1; for (int i = 2; i <= n; i++) { if (!isprime[i]) { prime[++cnt] = i; } for (int j = 1; j <= cnt && i * prime[j] <= n; j++) { isprime[i * prime[j]] = 1; if (i % prime[j] == 0) { break; } } } } ll getCount(int x, int n) { ll ans = 0; while (n) { ans += n / x; n /= x; } return ans; } int main() { int n; cin >> n; getPrime(n); ll ans = 1; for (int i = 1; i <= cnt; i++) { ll x = getCount(prime[i], n) * 2% mod; ans = ans * (x + 1)% mod; } cout << (ans + 1) * base % mod<< endl; return 0; }
