小V和方程

分析

考虑对 质因数分解，并将提取成的最简形式。
如果要满足，对于任意一个而言，化简后都带有。

于是问题被转化成能被表示为多少种个数的和，其中可以有。

也即个苹果放在个篮子里有多少种放法。

此处可用dp解， 表示个苹果放在个篮子里方法总数。

转移方程为

应牛友要求详细解释一下：

把5个苹果放进2个篮子里，我们已经知道了五个苹果放进一个篮子里有多少种方法，那么现在多出来了一个篮子，考虑篮子不空的情况，先把所有的篮子都放一个苹果，然后再加上3个苹果放进两个篮子里的方案数量。

也就是说对于， 是空了篮子的方案，是一个篮子都不空的方案。无论空多少个篮子呢，都包含在里面：这里是类似递归的理解，空一个篮子里包含了空一个篮子里的空一个篮子。

solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const ll mod = 998244353;
const int maxn = 1005;
ll dp[maxn][maxn];
ll f(ll n, ll m){  // m个苹果 n个篮子
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= m; ++j)
            if (j >= i)  dp[i][j] = (dp[i][j - i] + dp[i - 1][j]) % mod;
            else dp[i][j] = dp[j][j];
    return dp[n][m];
}
int main() {
    int n, m;
    cin >> n >> m;
    ll a = 1;
    for(ll i=2;i*i<=m;++i)
        while(m%(i*i)==0)a*=i,m/=(i*i);
    cout << f(n,a) << endl;
    return 0;
}