题目描述

题意:求不定方程$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$的正整数解的个数.
($x$,$y$为未知数,$n$为给定的数)

样例

输入样例: 1439 

输出样例: 102426508

线性筛素数(主要算法:数学推导)

下面是玄学数学推导时间:

因为
$$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$$
可以很轻松地看出 $\frac{1}{x}$和$\frac{1}{y}$是小于$\frac{1}{n!}$的,于是由小学知识可知$x$和$y$是大于$n!$的.

于是,我们令
$$y=n!+k (k\in \{N*})$$

于是,原式变为
$$\frac{1}{x}+\frac{1}{n!+k}=\frac{1}{n!}$$

两边通分,得
$$n! \times (n!+k)+x \times n!=x \times (n!+k)$$

整理,得
$$x=\frac{(n!)^{2}}{k}+{n!}$$

分析至此,已经比较明晰了.

因为$x$是正整数,则$\frac{(n!)^{2}}{k}+{n!}$也必须为正整数.

又因为${n!}\in\{N*}$,故只需$\frac{(n!)^{2}}{k}$为正整数即可.

由于$k$可以为任意正整数,故$k$只需取$(n!)^{2}$的约数即可.

此时$x=\frac{(n!)^{2}}{k}+{n!}$为正整数,$y=n!+k$也为正整数,故这样的$k$是满足题意的.

所以本题的实质其实是:
$$求(n!)^{2}的正约数个数和$$

玄学数学推导终于结束了…

接下来才是真正与算法有关的部分了.
我们知道,一个正整数可以被唯一分解为
$$N=p_1^{c_1} \cdot p_2^{c_2} \cdot p_3^{c_3} \cdots p_m^{c_m}$$

其中$c_i$均为正整数,$p_i$均为质数,且满足$p_1<p_2<p_3< \cdots <p_m$

则$N$的正约数个数为
$$(c_1+1) \cdot (c_2+1) \cdot (c_3+1) \cdot \cdots \cdot(c_m+1) = \prod_{i=1}^m (c_i+1)$$

所以我们只需找出所有的$c_i$即可.

为了提高效率,我们采用线性筛素数的方法,先找出$n!$的质因子,再通过分解质因数的方法找出所有的$c_i$即可.

注意我们这里只是找出了$n!$的所有的$c_i$,而题目要求的是$(n!)^{2}$的约数个数,所以统计时一定要乘2!!!!

因为平方过后,$n!$的所有$c_i$都变为了$2c_i$.(这个应该可以理解吧....)

还有一件事,记得取模(此事非常重要)!!!!

自此,你就完美的解决了这道题.

时间复杂度 $O(nlogn)$

C++ 代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MAX=1e6+1;
const ll mod=1e9+7;
ll n,ans=1;
ll c[MAX],prime[MAX];//c[i]为指数 
ll flag[MAX],s[MAX];
int tot;
inline void Linear()//线性筛素数 (查找1到n中每个数的最小质因子并记录位置)
{
    for(int i=2;i<=n;i++){
        if(!flag[i]){
            prime[++tot]=i;
            s[i]=tot;   
        }
        for(int j=1;j<=tot&&i*prime[j]<=n;j++){
            flag[i*prime[j]]=1;
            s[i*prime[j]]=j;// s[i] 表示 i 的最小质因子在prime数组中的位置 
            if(i%prime[j]==0)
                break;
        }
    }
}
inline void divide(int x)//将x分解质因数 
{
    while(x!=1){
        ++c[s[x]];//s[x]为x的最小质因子，c[s[x]]表示s[x]这个质因子的指数 
        x/=prime[s[x]];//分解 
    }
}
int main()
{
    scanf("%lld",&n);
    Linear();
    for(int i=1;i<=n;i++)
        divide(i);
    for(int i=1;i<=MAX;i++)
        if(c[i])
            ans=ans*(2*c[i]+1)%mod;//注意这里要乘二,因为最后统计的是n!的约数个数,而不是n!,所以所有的ci要变为2*ci
    printf("%lld\n",ans);
    return 0;
}
/*
*
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/