题解：P3861 拆分

· · 题解

题目大意

给定一个整数 n \ (2 \le n \le 10^{12})，求将 n 分解为互不相同且不小于 2 的整数的乘积的方案数，答案对 998244353 取模。

核心思路：01 背包方案计数

这道题的本质是一个变形的 01 背包方案计数问题。普通的 01 背包是“体积相加等于总容量”，而这里是“因数相乘等于总乘积”。物品是 n 的所有因数（除了 1 和 n 本身），每个因数只能用一次（题目要求互不相同），背包容积就是目标乘积 n。设 n 的因数集合为 fac，因子个数为 m。

状态转移

如果不考虑状态值域的大小，我们可以自然地定义二维状态 dp_{i, v}，表示从前 i 个因数中进行选择，乘积恰好为 v 的方案数。初始状态：dp_{0, 1} \gets 1（前 0 个物品乘积为 1 的方案数为 1）。状态转移方程：对于第 i 个因数 fac_i，我们可以选择不用它，或者用它（前提是 v 能被 fac_i 整除）。

dp_{i, v} \gets \left( dp_{i - 1, v} + dp_{i - 1, \frac{v}{fac_i}} \right) \bmod M

在普通的 01 背包中，因为第 i 层的状态只依赖于第 i - 1 层的数据，且每次转移都是从较小的体积转移到较大的体积，我们可以省略掉第一维 i，并通过倒序遍历体积 v 来保证每个物品只被使用一次。降维后的状态定义为 dp_v，表示乘积为 v 的方案数。对于每一个因数 fac_i，我们倒序遍历可能拼出的乘积 v，向前推导更新。

dp_{v \times fac_i} \gets (dp_{v \times fac_i} + dp_v) \bmod M

离散化状态值域

目标乘积 n \le 10^{12}，如果直接把乘积 v 作为数组下标，空间是完全无法承受的。

注意到一个重要性质：我们只关心那些能整除 n 的乘积 v，也就是说，状态的值域被严格限制在 n 的所有因数之中。因此，我们可以先求出 n 的所有因数并按从小到大排序。然后，将状态值域离散化，改为用因数在数组中的下标来转移，即用因数 fac_k 在离散数组中的下标 k 代替其真实的数值。

重新定义一维状态 dp_k 表示乘积为 fac_k 的分解方案数。初始状态变为：dp_0 \gets 1（因为 fac_0 = 1）。状态转移方程变为，对于外层正在遍历的因数 fac_i，我们倒序遍历前面已经拼出的乘积 fac_j：

dp_k \gets (dp_k + dp_j) \bmod M

其中 k 满足 fac_k = fac_i \times fac_j，且必须保证 fac_k 仍是 n 的因数。

由于 n \le 10^{12}，其因数个数 d(n) 在极值下不超过 6720 个。两层循环的时间复杂度为 O(d(n)^2)，看似可以通过。

常数优化：利用因子对称性进行数组映射

在实际实现状态转移时，我们面临一个问题：如何快速知道 fac_i \times fac_j 在数组中的下标 k？最直观的想法是用哈希表（如 std::unordered_map）来记录每个因数对应的下标。然而，在 O(d(n)^2) 的内层循环中，哈希表的常数较大，对于 T=5 且 n=10^{12} 的极限数据容易超时。我们需要进行常数优化。

利用因数成对出现的对称性，n 的因数必定成对分布在 \le \sqrt{n} 和 > \sqrt{n} 两侧。对于排序好的 fac 数组，其满足一个极为优美的对称性质：如果 x 的下标是 id_x，那么 \frac{n}{x} 的下标一定是 m - 1 - id_x。

因此我们只需要开一个大小为 \sqrt{n}（最大 10^6）的数组 id：

这样，我们将哈希查找转化为了数组寻址，虽然单次操作理论复杂度都是 O(1)，但常数优化巨大。时间复杂度 O(d(n)^2)，空间复杂度 O(\sqrt{n})。

代码实现

#include <bits/stdc++.h>
using namespace std;
using T = long long;
constexpr int M = 998244353;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        T n;
        cin >> n;

        // 预处理因数
        vector<T> fac;
        for (T i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                fac.push_back(i);
                if (i * i != n) fac.push_back(n / i);
            }
        }
        sort(fac.begin(), fac.end());

        int m = (int)fac.size();
        T sq = sqrt(n);

        // 获取任意因数在 fac 数组中的下标
        vector<int> id(sq + 2);
        for (int i = 0; fac[i] <= sq; i++) {
            id[fac[i]] = i;
        }
        auto get_id = [&](T x) {
            return x <= sq ? id[x] : m - 1 - id[n / x];
        };

        // 01 背包 DP
        vector<int> dp(m, 0);
        dp[0] = 1; 

        // 遍历所选因子，不能选 1 和 n 本身，所以下标从 1 到 m - 2
        for (int i = 1; i < m - 1; i++) {
            T rem = n / fac[i];
            int r = get_id(rem);

            // 倒序遍历容量，保证每个物品只选一次
            for (int j = r; j >= 0; j--) {
                if (rem % fac[j] == 0) { 
                    int k = get_id(fac[i] * fac[j]);
                    dp[k] += dp[j];
                    if (dp[k] >= M) dp[k] -= M;
                }
            }
        }
        cout << dp[m - 1] << '\n';
    }
    return 0;
}

撰写本题解时，该代码为最优解第二名。

AI 使用说明 本题解在写作完成后使用 Gemini 进行了润色。