题解 P1445 【[Violet]樱花】

2018-08-01 09:13:47


贡献一个用 $\LaTeX$ 写的比较美观的推导过程,如有错误请大佬指出。

将原方程做出以下变化:

将方程左边通分,得:

$$\frac{x+y}{xy}=\frac{1}{n!}$$

十字相乘,得:

$$n!(x+y)=xy$$

移项,得:

$$xy-n!(x+y)=0$$

两边同时加上 $(n!)^2$ ,得:

$$(n!)^2-n!(x+y)+xy=(n!)^2$$

左边因式分解,得:

$$(x-n!)(y-n!)=(n!)^2$$

设 $a=x-n!$ , $b=y-n!$ ,则有:

$$ab=(n!)^2$$

由唯一分解定理可知:

$$n!=p_1^{c_1}\times p_2^{c_2} \times ... \times p_k^{c_k}$$

那么有:

$$(n!)^2=p_1^{2c_1}\times p_2^{2c_2} \times ... \times p_k^{2c_k}$$

也就是说:

$$ab=p_1^{2c_1}\times p_2^{2c_2} \times ... \times p_k^{2c_k}$$

因为 $n!$ 是确定的,所以确定了 $a$ 、 $b$ ,就能确定 $x$ 、 $y$ 。

而且只要确定了 $a$ ,就能确定 $b$ 。

我们知道, $a$ 是 $(n!)^2$ 的因式。

那么 $a$ 的个数为:

$(2c_1+1)(2c_2+1)...(2c_k+1)$

那么最后的答案即为:

$$(2c_1+1)(2c_2+1)...(2c_k+1)\ mod\ 10^9+7$$

筛法筛一遍,然后把 $c_i$ 全部计算出来,最后统计答案即可。

代码细节见蒟蒻的blog