樱花

link

不要看原题面，不然你会被情侣虐成狗。看我的简述就行。

题面

人话 ： 求方程 $\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$ 的正整数解，答案对 $10^9+7$ 取模。其中 $n\in[1,10^6]$ 。

做法

注：以下所有 $x,y,n\in Z^+$ 我们先来对式子处理一下。可变为：

但我们又知道 求得 $x,y$ 其中之一就可以求出这一组正整数解，所以我们可以用函数的形式来表示出来：

还可以变 ：

但是这样看不出来什么，我们可以再化简，除去分子上的 $x$ ，可得：

如果要有正整数解，那么需要满足：

如果我们求得满足上面式子 $x-n!$ 的个数，那么我们就求得了 $x$ 的个数，我们也就求得了 $(x,y)$ 正整数解的个数。
我们又知道 $x-n!\mid (n!)^2$ 所以说我们就是要求 $(n!)^2$ 的约数个数，直接套公式即可：
设 $c$ 为 $(n!)^2$ 的约数个数，满足：
$(n!)^2=\sum\limits_{i=1}^{k}{{p_i}^{c_i}}$ 即可。

代码

#include<cstdio>
typedef long long LL;
#define NUMBER1 1000000
#define P(A) A=-~A
#define fione_i(begin,end) for(register int i=begin;i<=end;P(i))
const LL mod=1e9+7;
int prime[NUMBER1+5],n,cnt(0);
bool pd[NUMBER1+5];
inline void PRIME(){
    fione_i(2,n){
        if(!pd[i])prime[++cnt]=i;
        for(int j=1;prime[j]*i<=n;P(j)){
            pd[prime[j]*i]=true;
            if(!(i%prime[j]))break;
        }
    }
}
signed main(){
    LL p;
    scanf("%d",&n);
    PRIME();
    LL ans(1);
    fione_i(1,cnt){
        p=0;
        for(int j=n;j;j/=prime[i])p+=j/prime[i];
        ans=ans*((p<<1)+1)%mod;
    }
    printf("%lld",ans);
    return 0;
}