自动搬运

查看原文

来自洛谷，原作者为

	vegetabird **

搬运于2025-08-24 21:53:29，当前版本为作者最后更新于2017-08-10 17:06:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于每一个N，我们先求出它的第$i$小因子$fac_{i}$, 然后记录下因子$j$所对应的位置$pos_{j}$。这里有一个小技巧：

##+$if$ $j \le \sqrt{N}$, 则令$pos1_{j}=pos_{j}$

##+$if$ $j > \sqrt{N}$, 则令$pos2_{\frac{N}{j}}=pos_{j}$

这样就可以把空间压缩为$O(\sqrt{N})$

然后令$dp_{ij}$为把$fac_{i}$分解成若干个小于等于$fac_{j}$的数（包括$1$）的积的方案总数，则：

#$dp_{ij}=dp_{i j-1}$

#$if$ $i=j$, $dp_{ij}++$

#$if$ $fac_{i} \equiv 0,mod( fac_{j})$, $dp_{ij}+=dp_{pos_{\frac{fac{i}}{fac_{j}}} j-1}$

CODE:

#include<cstdio>
#include<cctype>
#include<cstring>
#include<utility>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<iostream>
#include<map>
using namespace std;
long long T,n;
long long fac[11000];
int dp[11000][11000];
const long long mod=998244353;
int pos1[1000010],pos2[1000010];
map<long long,int>ans;
int main(){
    cin>>T;
    register int i,j,s;long long q;
    while(T--){
        cin>>n;
        if(ans[n]){
            cout<<ans[n]<<endl;
            continue;
        }
        s=0;
        q=sqrt(n);
        if(n%q==0){
            fac[++s]=q;
            if(q*q!=n){
                fac[++s]=n/q;
            }
        }
        for(i=1;i<q;i++){
            if(n%i==0){
                fac[++s]=i;
                fac[++s]=n/i;
            }
        }
        stable_sort(fac+1,fac+s+1);
        for(i=0;i<=s;i++){
            for(j=0;j<=s;j++){
                dp[i][j]=0;
            }
        }
        for(i=1;i<=s;i++){
            dp[i][i]=1;
            if(fac[i]<=q){
                pos1[fac[i]]=i;
            }else{
                pos2[n/fac[i]]=i;
            }
        }
        for(i=1;i<=s;i++){
            for(j=1;j<=s;j++){
                dp[i][j]+=dp[i][j-1];
                if(i<=j){
                    continue;
                }
                if(fac[i]%fac[j]==0){
                    long long tmp=fac[i]/fac[j];
                    if(tmp<=q){
                        dp[i][j]+=dp[pos1[tmp]][j-1];
                    }else{
                        dp[i][j]+=dp[pos2[n/tmp]][j-1];
                    }
                    dp[i][j]%=mod;
                }
            }
        }
        cout<<dp[s][s]-1<<endl;
        ans[n]=dp[s][s]-1;
    }
}