【线性筛】阶乘约数

你的名字 2024-03-26 18:30 62阅读 0赞

**看老师写的DP看了一万年**

**终于有点会了**

题意：

![597c1378397f2be58a7114e70521a2f6.png][]

思路：

先去跑线性筛，把一个数的最小质因子是哪个给预处理出来，然后去跑DP

设num\[i\]表示 i 作为去掉最小质因子之后的数 的 在1\*2\*....\*n 的式子中该数的出现次数

cnt\[i\]表示 i 这个质因子在1\*2\*....\*n的式子中的出现次数

然后就可以递推了

然后按唯一分解去算出正约数个数就好了

还有一个很重要的点就是，**所有数可以看成是以质因子为根的森林，num数组的递推就相当于是从底层向根节点递推**

Code：

#include <bits/stdc++.h>
    //#define int long long
    #define LL long long
    const int mxn=1e6+10;
    const int mxe=2e5+10;
    const int mod=1e9+7;
    using namespace std;
    map<int,int> mp;
    int n,len=0;
    int prime[mxn],vis[mxn],cnt[mxn],num[mxn],d[mxn];
    void p_init(int n){
        for(int i=2;i<=n;i++){
            if(!vis[i]) prime[++len]=i,d[i]=i;
            for(int j=1;i<=n/prime[j];j++){
                vis[i*prime[j]]=1;
                d[i*prime[j]]=prime[j];
                if(i%prime[j]==0){
                    break;
                }
            }
        }
    }
    void solve(){
        //cnt[i]表示 i 在1*2*3*....*n这个式子里面i这个质因子的出现次数
        //num[i]表示 i 作为除去最小质因子的剩下的数 的 出现次数
        cin>>n;
        for(int i=2;i<=n;i++) num[i]=1;
        for(int i=n;i>1;i--){
            num[i/d[i]]=(num[i/d[i]]+num[i])%mod;
            cnt[d[i]]=(cnt[d[i]]+num[i])%mod;
        }
        for(int i=1;i<=n;i++) cout<<i<<" \n"[i==n];
        for(int i=1;i<=n;i++) cout<<num[i]<<" \n"[i==n];
        for(int i=1;i<=n;i++) cout<<cnt[i]<<" \n"[i==n];
        LL ans=1;
        for(int i=1;i<=n;i++){
            ans=(ans*(cnt[i]+1ll)%mod);
        }
        cout<<ans%mod<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        p_init(1e6);
        while(__--)solve();return 0;
    }

[597c1378397f2be58a7114e70521a2f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/8779e5fd51724bb98c96d4a0a5c60c51.png