【BZOJ2721】樱花（数论）

题面

BZOJ

题解

先化简一下式子，得到：\(\displaystyle n!(x+y)=xy\)，不难从这个式子中得到\(x,y\gt n!\)。
然后通过\(x\)来表示\(y\)，得到\(\displaystyle y=\frac{n!x}{x-n!}\)。令\(x=n!+p\)，得到\(\displaystyle y=\frac{n!(n!+p)}{p}=\frac{(n!)^2}{p}+n!\)。
因为\(x,y\)都是整数，得到\(p|(n!)^2\)。
于是问题变成了求约数个数，那么考虑每一个质因子的出现次数就行了。

#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 1000100
#define MOD 1000000007
int n,ans=1;
bool zs[MAX];
int main()
{
    cin>>n;
    for(int i=2;i<=n;++i)
        if(!zs[i])
        {
            for(int j=i+i;j<=n;j+=i)zs[j]=true;
            int p=n,s=0;
            while(p)s=(s+p/i*2)%MOD,p/=i;
            ans=1ll*ans*(s+1)%MOD;
        }
    cout<<ans<<endl;
    return 0;
}