【洛谷】P4167 [Violet]樱花

题面

又懒得弄题面，开个传送门吧

分析

人生第一次切数学题，我们先把方程写出来

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

现在我们知道的条件是x,y都是正整数（废话所以我们考虑单独通过式子的变换将x,y表示出来，表示出来的式子算出来也一定是个整数

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

$$\frac {1}{x}=\frac {1}{n!}-\frac{1}{y}$$

$$\frac {1}{x}=\frac {y-n!}{n!\times y}$$

$$x=\frac {n!\times y}{y-n!}$$

那么$\frac {n!\times y}{y-n!}$一定是一个整数

分母不太好看，不利于观察，所以假设$a=y-n!$,那么$y=a+n!$

那么原方程可以化简为

$$x=\frac {n!\times (a+n!)}{a}=\frac {n!\times a+n!\times n!}{a}=n!+\frac {n!\times n!}{a}$$

所以，如果$a$是$n!\times n!$的约数，根据$y=a+n!$与$x=n!+\frac {n!\times n!}{a}$可以知道x,y都是正整数

所以$n!\times n!$有多少个约数就有多少组解，直接分解质因数然后乘法原理计算就好了

Code

#include<cstdio>

int n,p[],unp[],mn[],mp[];

void prework()

{

    unp[]=;

    for(int i=;i<=;i++)

    {

        if(!unp[i])p[++p[]]=i,mn[i]=p[];

        for(int j=;1ll*p[j]*i<=;j++)

        {

            unp[p[j]*i]=;mn[p[j]*i]=j;

            if(i%p[j]==)break;

        }

    }

}

int main()

{

    prework();scanf("%d",&n);

    for(int i=;i<=n;i++)

    {

        int x=i;

        while(x>)mp[p[mn[x]]]++,x/=p[mn[x]];

    }

    int ans=;

    for(int i=;i<=n;i++)ans=1ll*ans*(mp[i]*+)%;

    printf("%d\n",ans);

}

巴特西

【洛谷】P4167 [Violet]樱花

最新文章

热门文章