[洛谷P1445][Violet]樱花

题目

题目描述

求方程
\frac{1}{X}+\frac{1}{Y}=\frac{1}{N!}
的正整数解的组数,其中N≤10^6。
解的组数,应模1e9+7。

输入格式

输入一个整数N

输出格式

输出答案

题解

部分内容参考自这篇文章

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

先通分

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

再化整数

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

然后配平

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

最后

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

然后我们发现x,y都要是正整数;

所以原题可以变为

A*B=(n!)^2

当\(A*B\)为正整数的时候\(x,y\)显然也是正整数;
\(x,y\)可以是任意正整数,即\(A,B\)可以为任意正整数,我们就可以对\(x\)单独进行讨论
我们考虑\(x\)的取值,显然,若一个质数\(p\)有\(k\)个,那么\(x\)可以取\(p^0,p^1….p^k\) 共\((k+1)\)种情况
乘法原理乘起来就可以了,而且显然,x确定后,y必然也会被确定
那么我们先可以筛出质数(这里是埃氏筛法);
求出每个数的最小质因数然后暴力就好了;

代码

发表评论

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