题解 P1445 【[Violet]樱花】
Creeper_LKF
2018-04-25 20:33:01
有没有感觉楼下的题解跑的不够快......
所以有没有什么快一点的呢?
那个4ms的12多k的是我的,然后目前除了在13年的记录之外Rnk1.
于是我们分析算法:
楼下题解的复杂度是O(nlogn+常数的),平均200ms
有没有什么更快的呢?
我们分析到了
```
A*B=(n!)*(n!)
```
的时候发现最终求的就是约数个数
首先如果求m的约数个数的话,那么对m分解得到
```
m=p1^k1*p2^k2...
```
其中p1,p2,p3...都是质数
那么根据乘法原理
```
Ans = (k1 + 1) * (k2 + 1)...
```
然后对于阶乘来说,对n!做质因数分解实则在分解1 * 2 * ... * n
然而这个就是楼下的做法,然而由于你实则是需要求质因数的指数,而在《初等数论》中有
![公式1](https://cdn.luogu.com.cn/upload/pic/18068.png)
所以我们直接递归(或者非递归地)跑这个公式即可
实际食用:枚举质数(或打表)(在阶乘下质因数等价于质数)(O(n)),然后对于所有质数,跑公式。
n内大约有n/ln(n)个质数,然后每次做都是log的,所以复杂度为O(n/ln(n) * log(n))=O(n),常数小,瓶颈在筛质数那......
代码如下(12kb不忍直视不敢放):
```
//Source Code
const int MAXN = 1000111;
const int MODS = 1000000007;
int n, tot;
int prime[MAXN];
bool is_not_prime[MAXN];
inline void Get_Prime(){
for(int i = 2; i <= n; i++){
if(!is_not_prime[i])
prime[++tot] = i;
for(int j = 1; j <= tot; j++){
if(i * prime[j] > n) break;
is_not_prime[i * prime[j]] = true;
if(!(i % prime[j])) break;
}
}
}
inline int Get_D(const int &tar, const int &p){
if(tar < p) return 0;
return tar / p + Get_D(tar / p, p);
}
int main(){
Main_Init();
n = read();
Get_Prime();
long long ans = 1;
for(int i = 1; i <= tot; i++)
(ans *= (Get_D(n, prime[i]) << 1) + 1) %= MODS;
write('\n', ans);
Main_Init();
return 0;
}
```