题解 | #小苯的前缀gcd构造#

1. 问题分析

该问题的核心在于构造一个数组 ，使其前缀 GCD 序列 的和等于目标值 。通过对 GCD 及其前缀性质的深入分析，我们可以得出以下关键约束：

• 单调不增性：由 的性质可知，。这意味着 必须是 的约数。因此，序列 必须是一个非递增的正整数序列。
• 整除约束：对于任意 ， 必须满足 。
• 范围约束：由于 ，且 ，推导出 。
• 权值合成：权值为 。
• 构造有效性：如果我们能找到满足上述条件的序列 ，我们直接令 即可满足条件。因为若 且 ，则 恒成立。

综上所述，问题转化为：寻找一个长度为 的序列 ，满足 ， 且该序列之和为 。

2. 算法：动态规划 (DP)

鉴于 的规模非常小（），且状态之间存在明显的层次结构和重叠子问题，动态规划是解决此类可行性构造问题的最优选择。

动态规划模型设计

• 状态定义： 表示是否存在一个长度为 的前缀序列，其最后一个元素 ，且序列元素的累加和为 。
  • ：当前处理的元素索引。
  • ：当前前缀 GCD 的值。
  • ：当前前缀和。
• 状态转移： 从长度 转移到 ： 其中需满足条件： 且 。
• 初始状态： 对于 ，设 。

路径回溯 (Path Reconstruction)

由于题目要求输出具体的构造方案，我们需要在 DP 填表后执行回溯。若存在某个 使得 ，则该 是可达的。从此状态出发，逆向寻找满足转移条件的 （即满足 且 ），逐步还原出整个序列。

3. 复杂度分析

• 时间复杂度：
  • 状态总数：。
  • 单状态转移：需遍历 的倍数，复杂度为 ，在 时其最大约数个数极小（ 有 个约数）。
  • 总复杂度大致为 。
• 空间复杂度：
  • 。

4. 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static bool dp[51][51][2501];

void solve() {
    int n, m, x;
    cin >> n >> m >> x;

    memset(dp, 0, sizeof(dp));
    for (int v = 1; v <= min(m, x); v++) {
        dp[1][v][v] = true;
    }

    for (int i = 2; i <= n; i++) {
        for (int v_pre = 1; v_pre <= m; v_pre++) {
            for (int s = 1; s <= x; s++) {
                if (!dp[i - 1][v_pre][s])
                    continue;

                for (int v_cur = 1; v_cur <= v_pre; v_cur++) {
                    if (v_pre % v_cur == 0 && s + v_cur <= x) {
                        dp[i][v_cur][s + v_cur] = true;
                    }
                }
            }
        }
    }

    int cur_v = -1;

    for (int v = 1; v <= m; v++) {
        if (dp[n][v][x]) {
            cur_v = v;
            break;
        }
    }

    if (cur_v == -1) {
        cout << -1 << endl;
        return;
    }

    vector<int> res;
    res.reserve(n);

    int cur_sum = x;
    for (int i = n; i >= 1; i--) {
        res.push_back(cur_v);

        if (i == 1)
            break;

        bool found = false;
        for (int v_pre = cur_v; v_pre <= m; v_pre += cur_v) {
            if (dp[i - 1][v_pre][cur_sum - cur_v]) {
                cur_sum -= cur_v;
                cur_v = v_pre;
                found = true;
                break;
            }
        }
    }

    reverse(res.begin(), res.end());
    for (int v : res) {
        cout << v << " ";
    }
    cout << endl;
}

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

    int T;
    cin >> T;

    while (T--) {
        solve();
    }
}