[BZOJ2721] [Violet 5] 樱花

题目

BZOJ 链接,需要权限
SPOJ链接,注册需要梯子
VJ链接
题目大意:求解方程 \frac{1}{x} + \frac{1}{y} = \frac{1}{n!} 有多少整数解。

 

思路

n! = z\ \ y = z + d
原式则为 \frac{1}{x} + \frac{1}{z + d} = \frac{1}{z}
移项 \frac{1}{z + d}\frac{1}{x} = \frac{d}{z(z+d)}
化简得 x = \frac{z^2}{d} + z
那么,一个 d 为一个解,问题变为求 z^2 的因子个数。
z^2 = p_1^{k_1} p_2^{k_2} ... p_q^{k_q}
那么因子个数为 (k_1+1)(k_2+1)...(k_q+1), 取摸即为答案。
在预处理筛素数的时候可以预处理出每个数最大的质因子,这样可以在穷举分解每一个数的时候提高效率,防止 T.

 

代码

 

完结

参考 黄学长博客

发表评论

电子邮件地址不会被公开。 必填项已用*标注