【题目来源】
洛谷：P3861 拆分 - 洛谷
【题目描述】
给定一个整数 \(n\)，求将 \(n\) 分解为互不相同的不小于 \(2\) 的整数的乘积的方案数。答案模 \(998244353\)。
【输入】
第一行一个整数 \(T\)，表示数据组数。
接下来 \(T\) 行，每行一个整数 \(n\)，意义如描述所述。
【输出】
一共 \(T\) 行，每行一个整数，表示答案。
【输入样例】
1
688
【输出样例】
6
【算法标签】
《洛谷 P3861 拆分》 #动态规划DP# #数论# #洛谷原创# #洛谷月赛# #O2优化#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005, mod = 998244353;
int t, n, cur, a[N];
int pos1[N], pos2[N];
int dp[7005][7005];
int k, pos, s;signed main()
{cin >> t;while (t--){cur = 0;memset(dp, 0, sizeof(dp));cin >> n;s = sqrt(n);// 找出n的所有因子for (int i = 1; i * i <= n; i++)if (n % i == 0){a[++cur] = i;if (i * i != n) // 避免重复添加平方数a[++cur] = n / i;}// 对因子排序sort(a + 1, a + cur + 1);// 建立因子的位置映射for (int i = 1; i + i <= cur + 1; i++){pos1[a[i]] = i; // 小于等于sqrt(n)的因子映射到前半部分pos2[a[i]] = cur + 1 - i; // 大于sqrt(n)的因子映射到后半部分}// 动态规划dp[1][1] = 1; // 从因子1开始for (int i = 1; i <= cur; i++)for (int j = 2; j <= cur; j++){dp[i][j] = dp[i][j-1]; // 不选第j个因子if (j > i) continue; // 保证因子递增if (a[i] % a[j] == 0) // 如果a[j]是a[i]的因子{k = a[i] / a[j]; // 计算比值if (k <= s)pos = pos1[k]; // 小因子位置else pos = pos2[n / k]; // 大因子位置dp[i][j] = (dp[i][j] + dp[pos][j-1]) % mod; // 状态转移}}cout << (dp[cur][cur] - 1 + mod) % mod << endl; // 输出结果} return 0;
}
【运行结果】
1
688
6