洛谷1445 [Violet]樱花

题意

求：

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

的正整数解 $(x,y)$ 的组数。

题解

对方程进行化简：

$$\dfrac {x+y}{x\times y}=\dfrac {1}{n!}$$

交叉相乘：

$$x\times y=n!\times (x+y)$$

化为 $y$ 的表达式：

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

显然 $x,y\geq n!$ ，不妨设 $x=n!+p$ ，则可化为：

$$y=\dfrac{n!^{2}}{p}+n!$$

因为 $x,y\in N^{\ast }$ ，所以 $p|n!^{2}$ ，那么求出 $n!^{2}$ 的约数个数即为答案。

剩下的就是标准的分解质因数了。

#include<bits/stdc++.h>
#define ll long long
#define ha 1000000007

using namespace std;

bool ss[1000005];
ll zs[200005],n,cnt,v[1000005],c[1000005],ans;

inline void get_prime()
{
    memset(ss,1,sizeof(ss));
    ss[0]=ss[1]=0;
    for (ll i=2;i<=n;i++)
    {
        if (ss[i])
        {
            zs[++cnt]=i;
            v[i]=i;
        }
        for (ll j=1;j<=cnt && zs[j]*i<=n;j++)
        {
            ss[zs[j]*i]=0;
            v[zs[j]*i]=zs[j];
            if (i%zs[j]==0) break;
        }
    }
}

int main()
{
    scanf("%lld",&n);
    get_prime();
    for (ll i=2;i<=n;i++) for (ll j=i;j>1;j/=v[j]) c[v[j]]++;
    ans=1;
    for (ll i=2;i<=n;i++) ans=ans*(c[i]*2+1)%ha;
    return !printf("%lld",ans);
}