学术区帖子传送门

原题传送门

如题

思路是分解 $n$ 的因数，记为 $d_1,d_2,...$，然后记 $f_{i,j}$ 表示将 $d_i$ 分解成几个不大于 $d_j$ 的数的乘积的方案数。

有没有哪位大佬可以看看，为什么样例会输出1?

代码附上：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int T;
long long n;
priority_queue<ll,vector<ll>,greater<ll> > q;
vector<ll> d;
ll f[6800][6800];
int pos1[1000010],pos2[1000010];
const long long mod=998244353;
void div(){
	for(ll i=1;i<=sqrt(n);++i){
		if(n%i==0){
			q.push(i);
			if(i*i==n){
				
			}
			else{
				q.push(n/i);
			}
		}
	}
	while(q.size()){
		d.push_back(q.top());//保证了d里面的数据从小到大排列
		q.pop();
	}
	for(int i=0;(i<<1)<=d.size();++i){
		pos1[d[i]]=i;//pos1[x]表示d[pos1[x]]=x
		pos2[d[i]]=d.size()-i-1;//pos2[x]表示d[pos2[x]]=n/x 这样做是为了减空间复杂度
	}
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%lld",&n);
		div();
		for(int i=0;i<d.size();++i){
			f[i][0]=(i==0);
			for(int j=1;j<d.size();++j){
				f[i][j]=f[i][j-1];//赋初值为d[i]分解不包含d[j]的方案数量
				if(j>i){
					break;
				}
				if(d[i]%d[j]==0){
					int pos,tmp=d[i]/d[j];
					if(tmp<=sqrt(n)){
						pos=pos1[tmp];
					}
					else{
						pos=pos2[n/tmp];
					}
					f[i][j]+=f[pos][j-1];
					f[i][j]%=mod;
				}
			}
		}
		printf("%lld\n",f[d.size()-1][d.size()-1]);
		d.clear();
	}
}