Luogu1445 [Violet]樱花
一句话题意：（本来就是一句话的）
求方程 $\frac{1}{X} + \frac{1}{Y} = \frac{1}{N!}$ 的正整数解的组数，其中$N \leq 10^6$
题解：
差不多是第一篇公开的题解，因为以前的太烂了，不敢发......
我们观察到提交记录发现似乎时间有从200ms+到8ms-的，然而标准题解中给出的代码就是跑的比较慢的......
所以有没有什么快一点的呢？
假设此时你已经用朴素算法A过此题
于是我们分析算法：
楼下题解的复杂度是$O(nlogn+常数的)$，平均200ms
有没有什么更快的呢？
假设我们分析到了
$A*B=(n!)*(n!)$
的时候发现最终求的就是约数个数
首先如果求m的约数个数的话，那么对m分解得到
$m=p_1^{k_1}*p_2^{k_2}...$
其中$p_1,p_2,p_3...$都是质数
那么根据乘法原理
$Ans = (k_1 + 1) * (k_2 + 1)...$
然后对于阶乘来说，对n!做质因数分解实则在分解1 * 2 * ... * n
然而这个就是朴素的做法，然而由于你实则是需要求质因数的指数，而在《初等数论》中有
$\Sigma(p \leq n, p \ is \ a \ prime)\Sigma_{k=0}^{p^k \leq n}(\lfloor \frac{n}{p^k} \rfloor)$
所以我们直接递归（或者非递归地）跑这个公式即可
实际食用：枚举质数（或打表）（在阶乘下质因数等价于质数）（O(n)），然后对于所有质数，跑公式。
n内大约有n/ln(n)个质数，然后每次做都是log的，所以复杂度为O(n/ln(n) * log(n))=O(n)，常数小，瓶颈在筛质数那......
代码如下：
//Source Code const int MAXN = ;
const int MODS = ; int n, tot;
int prime[MAXN];
bool is_not_prime[MAXN]; inline void Get_Prime(){
for(int i = ; i <= n; i++){
if(!is_not_prime[i])
prime[++tot] = i;
for(int j = ; 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 ;
return tar / p + Get_D(tar / p, p);
} int main(){
Main_Init();
n = read();
Get_Prime();
long long ans = ;
for(int i = ; i <= tot; i++)
(ans *= (Get_D(n, prime[i]) << ) + ) %= MODS;
write('\n', ans);
Main_Init();
return ;
}