【BZOJ2721】樱花(数论)

【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;
}
上一篇:三维重建


下一篇:浙大版《C语言程序设计(第3版)》题目集 习题3-5 三角形判断 (15 分)