[传送门]
推推式子
$$ \dfrac {1}{N!} = \dfrac{1}{X} + \dfrac{1}{Y} $$
$$ \dfrac {1}{X} = \dfrac{1}{N!} - \dfrac{1}{Y} $$
$$ \dfrac {1}{X} = \dfrac{Y - N!}{YN!} $$
$$ YN! = X(Y - N!) $$
$$ XN! = Y(X - N!) $$
$$ \therefore XY(N!)^2 = XY(N! - X)(N! - Y)$$
$$ \therefore (N!)^2 = (N!-X)(N! - Y) $$
把$N! - X$看成一个整体，那么题目就变成了求$(N!)^2$的约数个数了
因为要满足$X \leq Y$，那么答案就是约数个数除以2上取整
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 1e6 + 7; const int MOD = 1e9 + 7; int prime[N], prin; bool vis[N]; void getprime() { for (int i = 2; i < N; ++i) { if (!vis[i]) prime[++prin] = i; for (int j = 1; j <= prin && i * prime[j] < N; j++) { vis[i * prime[j]] = 1; if (i % prime[j] == 0) break; } } } int get(int n, int x) { int res = 0; int temp = x; while (n >= temp) { (res += n / temp) %= MOD; temp *= x; } return 2 * res % MOD; } signed main() { int n; scanf("%lld", &n); getprime(); int ans = 1; for (int i = 1; i <= prin && n >= prime[i]; i++) { int temp = get(n, prime[i]); //cout << i << ‘:‘ << temp << ‘\n‘; ans = ans * (temp + 1) % MOD; } printf("%lld\n", (ans + 1) * 500000004 % MOD); return 0; }
原文：https://www.cnblogs.com/Mrzdtz220/p/11664617.html
