「一本通 6.2 练习 5」樱花

求不定方程  $ \frac{1}{x}+\frac{1}{y}=\frac{1}{n!} $ 的正整数解$(x,y) $的数目.

analysis

首先先得化简式子，因为这个式子确实看不出来什么

一般看到的题解里有这两种化法：

first：

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

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

$xy=n!(x+y)$

$-n!(x+y)+xy=0\leftarrow\rightarrow(n!x+n!y)-xy=0$

对数学敏感的同学相信写到这一步时就已经可以发现一些东西了,这个式子是十字相乘法拆开括号的后两项!

若设$a=-n!,b=x,c=y$,则$a(b+c)+bc=0$,等式两边同时加上$a^2$

则$a^2+a(b+c)+bc=a^2,(a+c)(a+b)=a^2$

于是有$(x-n!)(y-n!)=(n!)^2$

也就是说$(x-n!)|(n!)^2$

那么,$(x-n!)$等价于$(n!)^2$的因子,又由于$(x-n!)$和x的个数相等,那么x的个数和$(n!)^2$的因子的个数一一对应

second：

设$y=n!+k$

则原方程为$x(n!+k)=n!(x+(n!+k))$

即$xn!+xk=n!(x+n!+k),xn!+xk=n!x+(n!)^2+n!k$

也就是$x=\frac{(n!)^2}{k}+n!$

也就是说x的个数等于$(n!)^2$的因子的个数

那么本题就是求$(n!)^2$的因子的个数

求因子个数,根据唯一分解定理的推论:

$x=\prod_{i=1}^{m}p_i^{s_i},p_i$是素数

x的约数个数$d(n)=\prod_{i=1}^{m}(s_i+1)$根据乘法原理可证明

对$ n! $ 唯一分解时可以用暴力,复杂度是$ O(\sum_{i=1}^{n} \sqrt{n}) $,应该是能过的.

但是上面的复杂度有点高,这里有更简单的方法.

    for(int i=1;i<=p[0];++i){
        for(LL j=p[i];j<=n;j*=p[i]) c[i]+=(n/j);
        c[i]%=mo;
    }

这么做为什么是对的呢?自已手动模拟一下就行了.还是要记住这个的.

总结,在遇到等式问题时,要多把等式转化为乘法形式,这样得到的信息比加法要多.

#include
using namespace std;
typedef long long LL;
const int mo=1000000007;
int n,p[1000006];
LL c[1000006];
bool vis[1000006];
void get_prime(){
    for(int i=2;i<=n;++i){
        if(!vis[i])
            p[++p[0]]=i;
        for(int j=1;j<=p[0]&&1LL*i*p[j]<=n;++j){
            vis[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}
int main(){
    scanf("%d",&n);
    get_prime();
    for(int i=1;i<=p[0];++i){//重点：求1~n之间约数的次幂 
        for(LL j=p[i];j<=n;j*=p[i]) c[i]+=(n/j);
        c[i]%=mo;//记住上面那个公式 
    }
    LL ans=1;
    for(int i=1;i<=p[0];++i)
    ans=(ans*(c[i]<<1|1))%mo;
    printf("%lld\n",ans);
    return 0;
    
}

暴力算法

#include
using namespace std;
typedef long long LL;
const int mo=1000000007;
int n,p[1000006],id[1000006];
LL c[1000006];
bool vis[1000006];
void get_prime(){
    for(int i=2;i<=n;++i){
        if(!vis[i]){
            p[++p[0]]=i;
            id[i]=p[0];
        }
        for(int j=1;j<=p[0]&&1LL*i*p[j]<=n;++j){
            vis[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}
int main(){
    scanf("%d",&n);
    get_prime();
    for(int i=1;i<=n;++i){
        int x=i;
        for(int j=1;j<=p[0];++j){
            if(1LL*p[j]*p[j]>x) break;
            while(x%p[j]==0) c[j]++,x/=p[j];
        }
        if(x>1) c[id[x]]++;  
    }
    LL ans=1;
    for(int i=1;i<=p[0];++i)
    ans=(ans*(c[i]<<1|1))%mo;
    printf("%lld\n",ans);
    return 0;
    
}