题目描述

给定 , 。

求 的本质不同解（可重集合）的个数。

正解

考虑把 表示成 的形式，其中 再也不能再进行拆分（没有平方因子）了。

那么 一定要是 的倍数。

现在题目就是一个划分数问题了（把 个相同的球放在 个相同的盒子内）， 递推即可。

代码

#include <bits/stdc++.h>

using namespace std;

const int mod = 998244353;

const int N = 1005;

int n, m, x, y;
int f[N][N];

int main() {
    scanf("%d %d", &n, &m);
    x = 1, y = 1;
    for(int i = 2; i * i <= m; ++i) {
        if(m % i) continue;
        int cnt = 1;
        for(m /= i; m % i == 0; m /= i) ++cnt;
        for(int j = 1; j <= cnt / 2; ++j)
            x *= i;
    }
    f[0][0] = 1;
    for(int i = 1; i <= n; ++i)
        for(int j = 0; j <= x; ++j) {
            f[i][j] = (f[i - 1][j] + (j - i >= 0 ? f[i][j - i] : 0)) % mod;
        }
    printf("%d\n", f[n][x]);
    return 0;
}