思路
我们可以很好的想到一种 \(O(nm)\) 的 dp:
状态：\(dp_{i,j}\) 为搜到第 \(i\) 个,最后一个数是 \(j\) 的方案数。
转移：\(dp_{i,j} = \displaystyle\sum_{k|j,k\not =j}dp_{i-1,k}\)
当然这是会超时的。
我们换一种思路，我们先枚举最后一个数，再计算方案数。
这有个好处，我们缩小了前面的数的范围，必定是最后一个数的因数。
我们先分解最后一个数的质因数，统计每个质因数的指数，质因数不超过 \(6\) 个。
然后我们将质因数分配给前面的数，这里的分配是指：假设我分配了 \(2\) 给一个数，则这个数是前面的一个数乘 \(2\)。
这样避免了前面的数不满足条件。
将质因数分配给前面的数，相当于 \(n\) 个小球,放进 \(m\) 个盒子里，可以留空。
也就是 \(\tbinom{m-1}{n+m-1}\) 。
最后将答案统计起来就好了
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+100,Mod=998244353;
int n,m,ans;
int fac[N+10],inv[N+10];
int qpow(int a,int b)
{
int res=1;
for(;b;a=a*a%Mod,b>>=1)
if(b&1)res=res*a%Mod;
return res;
}
int C(int n,int m){return n==m||m==0?1:fac[n]*inv[n-m]%Mod*inv[m]%Mod;}
signed main()
{
scanf("%lld%lld",&n,&m);
fac[1]=1ll;
for(int i=2;i<=N;i++)fac[i]=fac[i-1]*i%Mod;
inv[N]=qpow(fac[N],Mod-2);
for(int i=N-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%Mod;
for(int i=1;i<=m;i++)
{
int temp=i,tmp=1;
for(int j=2,cnt=0;j*j<=temp;j++)
{
cnt=0;
while(temp%j==0)cnt++,temp/=j;
tmp=tmp*C(cnt+n-1,n-1)%Mod;
}
if(temp!=1)tmp=tmp*n%Mod;
ans+=tmp,ans%=Mod;
}
cout<<ans;
}