题目
碎碎念：说好的提高+/省选-呢?
Solution
解：由题可知1/x+1/y = 1/n!，∴(x+y)/xy = 1/n!，∴xy = (x+y)*n!，∴(x-n!)(y-n!) = n!^2。
∵1/x+1/y = 1/n!且x,y为正整数，∴x,y > n!，所以x-n!,y-n! > 0。
令n! = p1^a1*p2^a2*...*pk^ak（复杂度O(nlogn)），则n!^2 = p1^2a1*p2*2a2*...*pk^2ak。
由因数个数定理得ans = d(n!^2) = (2a1+1)*(2a2+1)*...*(2ak+1)。
综上，ans = (2a1+1)*(2a2+1)*...*(2ak+1)，总时间复杂度O(nlogn)，空间复杂度O(n)。
Code
#include<cstdio>
#include<cstring>
#define MOD 1000000007
#define MAXN 1000001
#define MAXP 80001
using namespace std;
typedef long long LL;
int n, pri[MAXP], tot;
bool isp[MAXN];
LL ans = 1;
int calc(int n, int p){
int res = 0;
while(n) res += n /= p;
return res;
}
int main(){
scanf("%d", &n);
memset(isp, 1, sizeof isp);
isp[0] = isp[1] = false;
for(int i = 2;i <= n;i ++){
if(isp[i]) pri[tot ++] = i;
for(int j = 0;j < tot && i * pri[j] <= n;j ++){
isp[i * pri[j]] = false;
if(!(i % pri[j])) break;
}
}
// printf("%d", tot);
for(int i = 0;i < tot;i ++) ans = ans * (2 * calc(n, pri[i]) + 1) % MOD;
printf("%lld", ans);
}
