给定一个整数n，求有多少个x，y 满足1/x+1/y=1/n!
n ∈ [1,1e6]
# 题解
1 #include<bits/stdc++.h>
2 #define ll long long
3 using namespace std;
4 const int N=1e6+10,mod=1e9+7;
5 int n;
6 int p[N],cnt;
7 bool st[N];
8 void get_primes(int n){
9 for(int i=2;i<=n;i++){
10 if(!st[i]) p[cnt++]=i;
11 for(int j=0;p[j]*i<=n;j++) {
12 st[p[j] * i] = 1;
13 if(i% p[j]==0) break;
14 }
15 }
16 }
17 int main(){
18 cin>>n;
19 get_primes(n);
20 int ans=1;
21 for(int i=0;i<cnt;i++){
22 int sum=0;
23 int primes=p[i];
24 for(int j=n;j;j/=primes){
25 sum+=j/primes;
26 }
27 ans=(ll)(2*sum +1)%mod*ans%mod;
28 }
29 cout<<ans<<endl;
30 return 0;
31 }