SSOJ2904樱花[BZOJ2721]
1600+
作者：crxis 发布：2021-01-12 分类：数学
题目大意：不定方程$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$有多少对正整数解？
题目描述
原题来自：HackerRank Equations
求不定方程：$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$的正整数解 (x,y) 的数目。
输入
一个整数 n。
输出
一个整数，表示有多少对 (x,y) 满足题意。答案对 109+7 取模。
提示
样例输入
2样例输出
3样例说明
共有三个数对 (x,y) 满足条件，分别是 (3,6),(4,4) 和 (6,3)。
对于 30% 的数据，n≤100；
对于全部数据，1≤n≤106。
解题思路
化简公式，发现解的数量，就是$(n!)^2$的约数个数。
$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$
$\frac{x+y}{xy}=\frac{1}{n!}$
$(x+y){n!} = xy = xn! + yn!$
$x = \frac{yn!}{y-n!}$
不妨设x > y > n!，令y = n! + c，那么：
$x = \frac{yn!}{y-n!} = \frac{n!n!+cn!}{c} = \frac{n!n!}{c} + n!$
因此，只要c是$(n!)^2$的约数即可找到一组正整数解(x, y)。
程序实现
