时间限制: 1 Sec 内存限制: 128 MB
题目描述
qrc 参加了小兔的生日 party。小兔问了他一个问题……
小兔问：“给定一个关于 x 和 y 的方程：1/x+1/y=1/n!。给定 n 的值，计算这个方程有多少组正整数解？”
qrc：“这个问题太简单了，我不屑于做。”于是他把这道题扔给了你。
因为 qrc 会 extgcd，所以你只要告诉他解的个数除以 1000000007（1e9+7）的余数即可。
输入
一个正整数 n。
输出
一个数，表示解的个数。
样例输入
3
------
1439
样例输出
9
----
102426508
提示
对于前 20%的数据，n<=10。
对于前 40%的数据，n<=100。
对于前 60%的数据，n<=10000。
对于前 100%的数据，1<=n<=10000000。
题解
听到学弟们在群上交流他们自己出的题就来看看，意外发现这道题挺有意思，下面是我的做法。
先把式子化一化
$$frac{1}{x}+frac{1}{y}=frac{1}{n!}$$
$$frac{x+y}{xy}=frac{1}{n!}$$
$$xy=n!(x+y)$$
$$x=frac{n!y}{y-n!}$$
$$令z=y-n!$$
$$x=frac{n!(n!+z)}{z}$$
那么问题就变成求存在多少个正整数$z$能整除$n!(n!+z)$，由于$n!(n!+z)=n!^2+n!z$，其中$n!z$显然被$z$整除，我们只要考虑有多少个$z$能整除$n!^2$，那么我们把$1$到$n$都分解质因数，很容易求出$n!^2$的所有质因数个数，然后很容易就可以求出$n!^2$的因数个数，也就是答案，总复杂度可以做到$O(n)$。
代码
#include<cstdio> #define MN 10000000 #define MP 665000 #define MOD 1000000007 int n,ans=1,u[MN+5],p[MP+5],pn,s[MN+5],c[MN+5]; int main() { register int i,j; scanf("%d",&n); for(i=2;i<=n;++i) { if(!u[i])p[++pn]=u[i]=i; for(j=1;i*p[j]<=n;++j){u[i*p[j]]=p[j];if(i%p[j]==0)break;} } for(i=n;i>1;--i)c[u[i]]+=++s[i]<<1,s[i/u[i]]+=s[i]; for(i=1;i<=pn;++i)ans=1LL*ans*(c[p[i]]+1)%MOD; printf("%d",ans); }