luoguP1445 [Violet]樱花

链接P1445 [Violet]樱花

• 求方程 \(\frac {1}{X}+\frac {1}{Y}=\frac {1}{N!}\) 的正整数解的组数，其中\(N≤10^6\)，模\(10^9+7\)。
• 化简单一下$$xy-n!(x+y)=0$$
• 因式分解一下$$(x-n!)*(y-n!)=(n!)^2$$
• 设\(a=x-n!,b=y-n!\)，那么\(a*b=(n!)^2\)
• 也就是\(a,b\)对应了唯一一组\(x,y\)，所以问题转化成了：求方程 \(a*b=(n!)^2\) 的正整数解的组数。
• 考虑唯一分解定理，$$(n!)^2=\prod p_i^{2*c_i}$$
• 所以线性筛后分解\(n!\)，答案就是\(\prod (2*c_i+1)\)。

#include<bits/stdc++.h>

#define R register int

#define ll long long

using namespace std;

const int mod=1e9+7;

const int N=1000001;

int n,tot,ans,c[N],Mark[N],prm[N];

int gi(){

    R x=0,k=1;char c=getchar();

    while((c<'0'||c>'9')&&c!='-')c=getchar();

    if(c=='-')k=-1,c=getchar();

    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();

    return x*k;

}

int main(){

	n=gi(),ans=1;

	for(R i=2;i<=n;++i){

		if(!Mark[i])prm[++tot]=i;

		for(R j=1;j<=tot&&prm[j]*i<=n;++j){

			Mark[prm[j]*i]=1;

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

		}

	}

	for(R p=1;p<=tot;++p){

		R i=prm[p];

		for(R j=i;j<=n;j+=i){

			R x=j;

			while(x%i==0)c[i]++,x/=i;

		}

	}

	for(R i=1;i<=n;++i)c[i]=(c[i]<<1)+1;

	for(R i=1;i<=n;++i)ans=1ll*ans*c[i]%mod;

	cout<<ans<<endl;

    return 0;

}