题目

题目描述

求方程
$\frac{1}{X}+\frac{1}{Y}=\frac{1}{N!}$
的正整数解的组数，其中N≤10^6。
解的组数，应模1e9+7。

输入格式

输入一个整数N

输出格式

输出答案

题解

部分内容参考自这篇文章

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

先通分

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

再化整数

$xy-(x+y)*n!=0$

然后配平

$(n!)^2-(x+y)*n!+xy=(n!)^2$

最后

$(x-n!)*(y-n!)=(n!)^2$

然后我们发现 $x，y$ 都要是正整数；

所以原题可以变为

$A*B=(n!)^2$

当$A*B$为正整数的时候$x,y$显然也是正整数；
$x,y$可以是任意正整数，即$A,B$可以为任意正整数，我们就可以对$x$单独进行讨论
我们考虑$x$的取值，显然，若一个质数$p$有$k$个，那么$x$可以取$p^0,p^1....p^k$ 共$(k+1)$种情况
乘法原理乘起来就可以了,而且显然，x确定后，y必然也会被确定
那么我们先可以筛出质数（这里是埃氏筛法）；
求出每个数的最小质因数然后暴力就好了；

代码

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=1000005;
const int mod=1e9+7;
int n;
long long v[MAXN],phi[MAXN],p[MAXN],cnt;
int c[MAXN];

int main(){
    cin>>n;
    for(int i=2;i<=n;i++){
        if(v[i])continue;
        p[++cnt]=i;
        for(int j=1;j*i<=n;j++)v[i*j]=1;
    }
    long long k=0,ans=1;
    for(int i=1;i<=cnt;i++){
        int pri=p[i],c1=0;
        for(int j=n;j;j/=pri){
            c1+=j/pri;
        }
        c[++k]=c1;
    }
    for(int i=1;i<=cnt;i++)ans=ans*(c[i]*2+1)%mod;
    cout<<ans;
    return 0;
}

#include<iostream>

#include<cstdio>

using namespace std;

const int MAXN=1000005;

const int mod=1e9+7;

int n;

long long v[MAXN],phi[MAXN],p[MAXN],cnt;

int c[MAXN];

int main(){

cin>>n;

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

if(v[i])continue;

p[++cnt]=i;

for(int j=1;j*i<=n;j++)v[i*j]=1;

}

long long k=0,ans=1;

for(int i=1;i<=cnt;i++){

int pri=p[i],c1=0;

for(int j=n;j;j/=pri){

c1+=j/pri;

}

c[++k]=c1;

}

for(int i=1;i<=cnt;i++)ans=ans*(c[i]*2+1)%mod;

cout<<ans;

return 0;

}

发送评论编辑评论

题目

题目描述

输入格式

输出格式

题解

代码

发送评论 编辑评论

发送评论编辑评论