【线性筛】阶乘约数

看老师写的DP看了一万年

终于有点会了

题意：

思路：

先去跑线性筛，把一个数的最小质因子是哪个给预处理出来，然后去跑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;
}