首页 > 代码库 > [9018]2006: 方程狂魔

[9018]2006: 方程狂魔

时间限制: 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);
}

 

[9018]2006: 方程狂魔