题意

给定一个整数n，求有多少正整数对(x, y)满足$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$

思路

推公式
$$\begin{gathered} \because \frac{1}{x}+\frac{1}{y}=\frac{1}{n!} \\ . \\ \therefore x\ge n!y\ge n! \\ . \\ \therefore y=k+n!(k\ge 1) \\ . \\ \frac{1}{x}+\frac{1}{y}=\frac{1}{n!}->\frac{1}{x}+\frac{1}{k+n!}=\frac{1}{n!} \\ . \\ \therefore n!\ast (n!+k)+x\ast n!=x\ast (n!+k) \\ . \\ x=\frac{n{1}^2}{k}+n! \\ . \\ \because x\in N^{\ast } \\ . \\ \therefore n{!}^{2}modk=0 \end{gathered}$$

综上我们只需要求出$n{!}^2$所有得约数然后利用公式求出约数个数就是最终的答案。而Acwng基础课中有求阶乘的所有约数。

代码

#include<bits/stdc++.h>#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define int long long
#define endl "\n"
#define xx first
#define yy secodusing namespace std;typedef pair<int, int> PII;const int N = 1e6 + 10, mod = 1e9+7;int n, m, k, _, cnt;
int arr[N], p[N];
bool st[N];void is_prime()
{for(int i = 2; i < N; i ++){if(!st[i]) p[cnt++] = i;for(int j = 0; p[j]*i < N; j ++){st[i*p[j]] = 1;if(i % p[j] == 0) break;}}
}signed main()
{IOS;is_prime();map<int, int> mp;cin >> n;int ans = 1;for(int i = 0; i < cnt; i ++){int t = p[i];int res = 0;for(int j = n; j; j /= t) res += j/t;ans = ans * (res * 2 + 1) % mod; //因为是平方所以*2}cout << ans << endl;return 0;
}