P1445 [Violet] 樱花 讲解

· · 题解

题意：

给你一个数 n(1\le n\le 10^6)， 求：

\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}

的解数。

进入正题：

先推式子：

\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}

通分， 得：

\frac{x}{xy}+\frac{y}{xy}=\frac{1}{n!} \frac{x+y}{xy}=\frac{1}{n!}

整理， 得：

(x+y)n!=xy xn!+yn!=xy

移项， 得：

xy-xn!-yn!=0

配方， 得：

xy-xn!-yn!+n!^2=n!^2 (x-n!)(y-n!)=n!^2

然后我们就把这个问题转化为了 “n!^2 有几个因数”， 又因为求因数和公式：

n=a_1^{q_1}a_2^{q_2}\dots\dots a_i^{q_i} m=(q_1+1)(q_2+1)\dots\dots (q_i+1)

得：

m^2=(2q_1+1)(2q_2+1)\dots\dots (2q_i+1)

故首先要筛质数， 然后再分解质因数， 最后统计即可。
代码： 

#include<bits/stdc++.h>
#define INF 214748364721474836
#define int long long
#define endl '\n'
#define inl inline
#define reg register
using namespace std;
const int N=1e6+5,MOD=1e9+7;
int n,prime[N],cnt,ans=1,sum[N];
bool vis[N];
inl int read(){
    reg int f=1,x=0;
    reg char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return f*x;
}
inl void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>=10) write(x/10);
    putchar(x%10^48);
}
signed main(){
    n=read();
    for(reg int i=2;i<=n;++i)
        if(!vis[i]){
            prime[++cnt]=i;
            for(reg int j=i;j<=n/i;++j) vis[i*j]=true;
        }
    for(reg int j=1;j<=cnt;++j){
        int x=n;
            while(x){
                sum[j]+=x/prime[j];
                x/=prime[j];
        }

            }
    for(reg int i=1;i<=cnt;++i) ans=(ans*(sum[i]<<1|1))%MOD;
    write(ans);
    return 0;
}