关于唯一分解定理的一些推导

· · 个人记录

前言

已知唯一分解定理基础形式：

可得: $N$ 因子个数（ 记为 $f(N)$ ）为 $ C_{b_1+1}^{1}\times C_{b_2+1}^{1}\times C_{b_3+1}^{1}\times \cdots\times C_{b_i+1}^{1} $ （共 $a_i$ 项）——即: $ f(N)=\prod \limits_{i=1}^{ai}C_{b_i+1}^{1}=\prod \limits_{i=1}^{ai}(b_i+1)

，这个式子是恒成立的。

有了上述基础，我们可以将 N 特殊化，改为 n! ，式子就会转化为:

1\times 2\times 3\times \cdots\times n=P_{a_1}^{b_1}\times P_{a_2}^{b_2}\times \cdots\times P_{n}^{b_i}=2^{b_1}\times 3^{b_2}\times \cdots\times P_{n}^{b_i}

此时上方求因子个数的公式仍然成立，不难发现， f(n!) 只与其质因子有关，且只差一个 b_i 就能很轻松地算出 f(n!)。

那么知道了上述的依托答辩结论有什么用呢？

应用

洛谷P1445

碰到此类的数学题首想就是化简式子，又鉴于有 x、y两个未知数， n\le 10^6 还带阶乘，因此直接将 x 用 n 表示出来即可。

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

首先移项：

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

即：

\frac{1}{x}=\frac{y-n!}{y\times n!}

其次倒一下数，上下换一换(相当于将 x 那边化成整数)：

x=\frac{y\times n!}{y-n!}

最后分离常数:

x=\frac{n!\times ( y-n! ) +(n!)^2}{y-n!}

即：

x={n!}+\frac{(n!)^2}{y-n!}

由于题目要求 x、y 必须为正整数，很容易知道 (y-n!) 为 (n!)^2 的因子，按照我们前面推得的结论，代入公式：

&=P_{a_1}^{b_1}\times P_{a_2}^{b_2}\times \cdots\times P_{a_i}^{b_i}\times P_{a_1}^{b_1}\times P_{a_2}^{b_2}\times \cdots\times P_{n}^{b_i}\\ &=P_{a_1}^{b_1\times 2}\times P_{a_2}^{b_2\times 2}\times \cdots\times P_{n}^{b_i\times 2}\\ &= \prod \limits_{i=1}^{n}(2\times b_i+1)\end{aligned}

所以我们直接枚举出 n 的所有质因子（反正是阶乘所以就不用分解质因数了）出现的次数最后乘个 2 加个 1 就行了( 别忘了取模! )。

Code

#include<bits/stdc++.h>
#define N 9555555
#define ll long long
using namespace std;
const ll mod = 1e9+7;
ll n,ans=1,lis[N],k;
bool table[N];
void solve(){       //筛法筛出质数
    for(int i=2;i<=n;i++){
        if(table[i]==0)
            lis[++k]=i;
        for(int j=1;j<=k&&i*lis[j]<=n;j++){
            table[i*lis[j]]=1;
            if(i%lis[j]==0)
                break;
        }
    }
    return ;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    solve();
    for(ll i=1;i<=k;i++){       //套公式
        ll t=n,p=lis[i],sum=0;
        while(t>1){
            t/=p;
            sum+=t;
        }
        //cout<<sum<<'\n';
        ans*=2*sum%mod+1;
        ans%=mod;
    } 
    cout<<ans;
    return 0;
}

据说这个结论也可以用于P5150里--->题目传送门（逃

完结撒花QWQ