Luogu P1445 [Violet] 樱花 题解

前言

题目传送门 Luogu P1445 [Violet] 樱花
最好写蓝题。
题意

求不定方程

\[\frac{1}{x} + \frac{1}{y} = \frac{1}{n!}\]
的正整数解 \((x,y)\) 的数量。
答案对 \(10^9+7\) 取模。保证 \(1\le n\le 1\times 10^6\) 。
思路

首先，我们对原方程进行化简。（超详细不跳步推理！包你看懂！）

\[\begin{align*}\frac{1}{x} + \frac{1}{y} &= \frac{1}{n!}\\\frac{x+y}{xy} &= \frac{1}{n!}\\\frac{xy}{x+y} &= n!\\xy &= xn! + y n!\\xn!+yn!-xy &= 0\\xn!+yn!-xy+n!^2 &= n!^2\\-x(y-n!) + n!(y+n!-2n!)+2n!^2 &= n!^2\\(y-n!)(n!-x) &= -n!^2\\(x-n!)(y-n!) &= n!^2\end{align*}\]
p.s. 这道题其实已经解决了，不信你试着自己做一下
还不明白？我们看最后一个柿子，它告诉我们，只要满足 \((x-n!) \mid n!^2\) ，那么这个 \(x\) 就是一个合法解，同时，也对应了一个合法的 \(y\) 。说得更明白些，就是 \(n!^2\) 有多少个因子，就有多少组合法解。
那么我们只要求 \(n!^2\) 的约数个数即可。需要掌握约数个数定理。
事实上，我们并不需要真的求出阶乘，只需要对 \(2\sim n\) 的每个数分解质因数并统计质因数的次数即可。看数据范围，\(n\le 10^6\) ，那么试除大法都可以解决。实测洛谷最大的一个点可以在 \(500ms\) 内过掉。而且试除法代码极短，非常好写。不信你看：
代码

[code]#include#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);#define MIKU 0using namespace std;const int MOD = 1e9 + 7;int n, ans = 1;int pw[1000005];void fac(int a) {        for(int i=2; i*i>n;        for(int i=2; i

感谢发布原创作品，程序园因你更精彩