[Violet]樱花

洛咕

题意:求方程(1/X+1/Y=1/(N!))的正整数解的组数，其中(N≤10^6).

分析:大力推式子.首先看到分数想到通分得,(yn!+xn!=xy),移项得(xy-(x+y)n!=0)

式子两边同时加上((n!)^2),得到((n!)^2-(x+y)n!+xy=(n!)^2)

左边十字相乘得((x-n!)(y-n!)=(n!)^2)

令(a=x-n!,b=y-n!),得(ab=(n!)^2)

因为(n!)可以由算数基本定理得(p_1^{c_1}p_2^{c_2}...p_k^{c_k})

所以((n!)^2=ab=p_1^{2c_1}p_2^{2c_2}...p_k^{2c_k})

因为知道了a,b就能知道x,y,而从上式可以看出知道了a,就能知道b.换而言之,a,b一一对应,a,b又分别和x,y一一对应,所以求满足条件的(x,y)等价于求a的个数.

因为a是((n!)^2)的因子，根据算数基本定理的推论得，a的个数是((2c_1+1)(2c_2+1)...(2c_k+1))个.

所以我们只要将(n!)质因数分解求出所有的c就可以了.但是(n!)是非常大的,所以我们并不能直接来求,这里需要掌握阶乘分解的方法,推荐一篇博客.

#include<bits/stdc++.h>
#define LL long long
using namespace std;
inline LL read(){
    LL s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*w;
}
const LL mod=1e9+7;
const LL N=10000005;
LL n,m,tot,ans=1;
LL prime[N],v[N],c[N];
inline void get_Prime(){
    for(LL i=2;i<=n;i++){
		if(v[i]==0){
	    	v[i]=i;
	    	prime[++m]=i;
		}
		for(LL j=1;j<=m;j++){
	    	if(prime[j]>v[i]||prime[j]*i>n)break;
	    	v[prime[j]*i]=prime[j];
		}
    }
}
int main(){
    n=read();get_Prime();
    for(LL i=1;i<=m;i++){
        LL p=prime[i];
        for(LL j=p;j<=n;j*=p)c[i]+=(n/j);
        c[i]%=mod;
    }
    for(LL i=1;i<=m;i++)ans=(1LL*ans*(c[i]*2+1))%mod;
    printf("%lld
",(ans%mod+mod)%mod);
    return 0;
}