题解 P1445 【[Violet]樱花】

有没有感觉楼下的题解跑的不够快...... 所以有没有什么快一点的呢？ 那个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 然而这个就是楼下的做法，然而由于你实则是需要求质因数的指数，而在《初等数论》中有  所以我们直接递归（或者非递归地）跑这个公式即可 实际食用：枚举质数（或打表）（在阶乘下质因数等价于质数）（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; } ```