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;
}