当前位置:首页 > 数学 > 正文
SSOJ2904樱花[BZOJ2721]
1078+

题目大意:不定方程$\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% 的数据,n100
对于全部数据,1n106

解题思路

化简公式,发现解的数量,就是$(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)。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,,

SSOJ2904樱花[BZOJ2721]:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!