过分简单的一道数论题，然而想了很长时间才做出来，记录一下。
问题为求：
可以考虑直接通分变形：
然后十字开项：
接着同时加上$n!$后移项：
然后进行十字相乘：
于是当前的问题就转变成了如何求 $(n!)^2$ 的约数个数。
约数公式在算数基本定理中有叙述，我们可以首先考虑 $(n!)^2$ 分解出来的每个质数从 $p^c$ 变成了 $p^{2c}$，那么约数公式就变成了：
因此我们只需要对 $n!$ 进行质因数分解即可，此时可以考虑针对 $1-n$ 的每个数分解。
同样在算数基本定理中叙述了几种高效的质因数分解方法，这题就可以迎刃而解了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include<bits/stdc++.h>
using namespace std;
int Prime[1000050],isPrime[1000050],c[1000050],cnt;
void GetPrime(int n){
for(int i=2;i<=n;++i){
if(!isPrime[i]){
isPrime[i]=i;
Prime[++cnt]=i;
}
for(int j=1;j<=cnt&&i*Prime[j]<=n;++j) {
isPrime[i*Prime[j]]=Prime[j];
if(i%Prime[j]==0)break;
}
}
}
int main(){
int n;
long long ans=1;
cin>>n;
GetPrime(n);
for(register int i=2;i<=n;++i)
for(register int j=i;j!=1;j/=isPrime[j])
++c[isPrime[j]];
for(register int i=2;i<=n;++i){
ans*=(c[i]*2+1);
ans%=1000000007;
}
cout<<ans<<endl;
}
|