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\) 内过掉。而且试除法代码极短，非常好写。不信你看：

代码

#include<iostream>
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define MIKU 0
using namespace std;

const int MOD = 1e9 + 7;
int n, ans = 1;
int pw[1000005];

void fac(int a) {
	for(int i=2; i*i<=a; i++) while(a % i == 0) a /= i, pw[i] ++;
	if(a != 1) pw[a] ++;
}

int main() {
	fastio;
	cin>>n;
	for(int i=2; i<=n; i++) fac(i);
	for(int i=1; i<=n; i++) {
		pw[i] *= 2;
		ans = ((ans % MOD) * ((pw[i] + 1ll) % MOD)) % MOD;
	}
	cout<<ans;
	return MIKU;
}

后记

当然你也可以用线性筛去做，比试除法快得多，代码也不长。其实是我懒得改了（逃

但是试除大法好！