我很愤怒
求方程 $\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}{x*y}=\frac{1}{n!}$
$xy-(x+y)*(n!)=0$
$(n!)^2+xy-(x+y)*n!=(n!)^2$
$(x-n!)*(y-n!)=(n!)^2$
设$t=(n!)$
$(x-t)*(y-t)=t^2$
∵$x,y$是正整数，∴$x-t>0$且$y-t>0$
（若要小于0，则$(x-t)$和$(y-t)$中至少要有一个小于$-t$，也就是$x<0$或$y<0$，与题设不符
设$A=(x-t)$，$B=(y-t)$
则有$A*B=t^2=(n!)^2$
所以$A$的方案数就是$(n!)^2$的因子数，也就是一些质因子乘起来的结果。
所以把$(n!)^2$分解质因数，设为$(n!)^2={a_1}^{p_1}*{a_2}^{p_2}...*{a_m}^{p_m}$
则答案为$(p_1+1)*(p_2+1)*...*(p_m+1)$。
1 qwerta 2 P1445 [Violet]樱花 Accepted 3 100 4 代码 C++，0.54KB 5 提交时间 2018-10-23 22:08:48 6 耗时/内存 86ms, 2692KB 7 #include<iostream> 8 #include<cstdio> 9 using namespace std; 10 bool sf[1000003]; 11 int p[1000003]; 12 int main() 13 { 14 int n; 15 scanf("%d",&n); 16 int tos=0; 17 for(int i=2;i<=n;++i) 18 if(!sf[i]) 19 { 20 p[++tos]=2;//因为是(n!)的平方，所以次数+=2 21 for(int j=2;i*j<=n;++j) 22 { 23 int x=i*j; 24 sf[x]=1; 25 while(x%i==0) 26 { 27 p[tos]+=2; 28 x/=i; 29 } 30 } 31 } 32 /* 33 for(int i=2;i<=n;++i) 34 { 35 int x=i; 36 for(int j=1;j<=tos&&x>1;++j) 37 { 38 while(x%st[j]==0) 39 { 40 p[j]+=2; 41 x/=st[j]; 42 } 43 } 44 } 45 */注释掉的是暴力分解2~n的质因数，亲测T上天 46 long long ans=1,mod=1e9+7; 47 for(int i=1;i<=tos;++i) 48 ans=(ans*(p[i]+1))%mod;//统计答案 49 cout<<ans; 50 return 0; 51 }
转载于:https://www.cnblogs.com/qwerta/p/9841719.html
相关资源：JAVA上百实例源码以及开源项目