【每日一题】P3861 拆分

题目描述

给定一个整数 $n$，求将 $n$ 分解为互不相同的不小于 $2$ 的整数的乘积的方案数。答案模 $998244353$。

输入格式

第一行一个整数 $T$，表示数据组数。

接下来 $T$ 行，每行一个整数 $n$，意义如描述所述。

输出格式

一共 $T$ 行，每行一个整数，表示答案。

输入输出样例 #1

输入 #1

1
688

输出 #1

6

说明/提示

样例中，因为

$688 = 2 \times 4 \times 86= 2 \times 8 \times 43= 2 \times 344= 4 \times 172= 8 \times 86= 16 \times 43$

所以答案为 $6$

对于 $10\%$ 的数据，保证 $n$ 为质数

对于 $20\%$ 的数据，保证 $2 \leq n \leq 10^4$

对于 $50\%$ 的数据，保证 $2 \leq n \leq 10^7$

对于 $100\%$ 的数据， 保证 $2 \leq n \leq 10^{12}$

所有数据满足 $1 \leq T \leq 5$

参考代码

by -

#include <iostream>
#include <cmath>
using namespace std;

typedef long long LL;

const LL MaxId = 7050;
const LL Maxsq = 1e6 + 5;
const LL Mo = 998244353;

LL v_value[MaxId], v_pos1[Maxsq], v_pos2[Maxsq], dp[MaxId][MaxId];

void init(LL cnt, LL num) {
    for (LL i = 0; i <= cnt; ++i) {
        for (LL j = 0; j <= cnt; ++j)
            dp[i][j] = 0;
    }
    for (LL i = 0; i <= num; ++i)  v_pos1[i] = v_pos2[i] = 0;
}

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

    LL t, n, cnt = 0, num = 0;
    cin >> t;

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

        cnt = 0;
        for (LL i = 1; i * i <= n; ++i) {
            if (n % i == 0)  v_value[++cnt] = i;
        }
        for (LL i = sqrt(n); i >= 1; --i) {
            if (n % i == 0 && n / i != i)  v_value[++cnt] = n / i;
        }

        init(cnt, sqrt(n));
        for (LL i = 1; i <= cnt; ++i) {
            if (v_value[i] <= sqrt(n)) v_pos1[v_value[i]] = i;
            else  v_pos2[n / v_value[i]] = i;
        }

        for (LL i = 1; i <= cnt; ++i) {
            dp[i][i] = 1;
            for (LL j = 1; j <= cnt; ++j) {
                dp[i][j] = (dp[i][j] + dp[i][j - 1]) % Mo;
                if (i > j && v_value[i] % v_value[j] == 0) {
                    num = v_value[i] / v_value[j];
                    if (num <= sqrt(n))  dp[i][j] = (dp[i][j] + dp[v_pos1[num]][j - 1]) % Mo;
                    else  dp[i][j] = (dp[i][j] + dp[v_pos2[n / num]][j - 1]) % Mo;
                }
            }
        }

        cout << dp[cnt][cnt] - 1 << '\n';
    }

    return 0;
}

参考代码yzy

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int M = 998244353;

map<ll, int> ans; 

void slv() {
    ll n;
    cin >> n;

    if (ans.count(n)) {
        cout << ans[n] << endl;
        return;
    }

    vector<ll> d;
    ll sq = sqrt(n);
    for (ll i = 1; i <= sq; ++i) {
        if (n % i == 0) {
            d.push_back(i);
            if (i * i != n) {
                d.push_back(n / i);
            }
        }
    }
    sort(d.begin(), d.end());

    int sz = d.size();
    vector<vector<int>> dp(sz, vector<int>(sz, 0));
    

    vector<int> p1(sq + 2, 0);
    vector<int> p2(sq + 2, 0);

    for (int i = 0; i < sz; ++i) {
        dp[i][i] = 1; 
        if (d[i] <= sq) {
            p1[d[i]] = i;
        } else {
            p2[n / d[i]] = i;
        }
    }

    for (int i = 1; i < sz; ++i) { // 遍历每个待构成的数 d[i]
        for (int j = 1; j < sz; ++j) { // 遍历可选的因子 d[j]
            // 方案继承自不选 d[j] 的情况
            dp[i][j] = (dp[i][j] + dp[i][j - 1]) % M;

            // 只有当 d[j] < d[i] 时，d[j] 才可能是 d[i] 的一个真因子
            if (d[i] > d[j] && d[i] % d[j] == 0) {
                ll rem = d[i] / d[j];
                int k; // 剩余部分 rem 的下标

                if (rem <= sq) {
                    k = p1[rem];
                } else {
                    k = p2[n / rem];
                }
                
                // 加上选择 d[j] 的方案数
                dp[i][j] = (dp[i][j] + dp[k][j - 1]) % M;
            }
        }
    }
    
    // 最终答案是构成 n 的方案数减去 n 本身这一种
    int res = (dp[sz - 1][sz - 1] - 1 + M) % M;
    cout << res << endl;
    ans[n] = res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--) {
        slv();
    }

    return 0;
}