[BOZJ2721]樱花

题目求\(\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}\)已知n, x和y的正整数解的个数

设z=\(n!\)

\(\frac{1}{x}+\frac{1}{y}=\frac{1}{z}\)

\(x=\frac{yz}{y-z}\)

令\(t=y-z\)则\(x=\frac{z(t+z)}{t}=\frac{zt+z^2}{t}=z+\frac{z^2}{t}\)

当t为整数时 x,y有整数解

故求出\(z^2\)的因数即可

运用约数和公式和线性筛即可

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const ll mo=1e9+7;

ll t,ans,tot,x,n;

ll prime[500005],f[1000005];

void init(ll x)

{

	t=0;

	for(ll i=2;i<=x;i++)

	{

		if(!f[i])prime[++t]=i;

		for(ll j=1;j<=t;j++)

		{

			if(prime[j]*i>x)break;

			f[prime[j]*i]=1;

			if(i%prime[j]==0) break;

		}

	}

}

int main()

{

	scanf("%lld",&n);

	init(n);ans=1;

	for(ll i=1;i<=t;i++)

	{

		tot=0;x=n;while(x){tot=tot+x/prime[i];x/=prime[i];}

		ans=ans*(tot*2+1)%mo;

	}

	printf("%lld",ans);

	return 0;

}

巴特西

[BOZJ2721]樱花

最新文章

热门文章