ACGO巅峰赛#22+题解

解题思路

1. 初始最大公因数
   先计算整个数组的最大公因数为

   $$g = \gcd(a_1, a_2, \ldots, a_n)$$

2. 操作效果分析
   操作步骤：

   • 选定一个子序列，其最大公因数为 $g_s$。
   • 对子序列中每个元素 $a_{b_i}$ 变为

     $$a'_{b_i} = \frac{a_{b_i} \times (g_s + 1)}{g_s}$$

   因为 $g_s \mid a_{b_i}$，分数是整数。

3. 操作后数组最大公因数的变化
   设操作后整体数组最大公因数为 $G'$，子序列中元素的变化相当于将它们乘以 $\frac{g_s + 1}{g_s}$。

   目标是选取子序列使得 $G'$ 最大。

4. 关键观察

   • 操作只进行一次。
   • 选择子序列对应的最大公因数 $g_s$ 必须满足：
     $g_s$ 是数组中某些元素的最大公因数。
   • 操作后，子序列元素的公因数变为 $g_s+1$。
   • 其他未选元素保持不变，最大公因数变为这些元素与操作后子序列元素公因数的 $\gcd$。

5. 转化

   • 假设未选元素的最大公因数为 $g_{rest}$。
   • 操作后整体最大公因数为

     $$G' = \gcd(g_s + 1, g_{rest})$$

   • 为了最大化 $G'$，枚举所有可能的 $g_s$：
     • $g_s$ 是数组中存在的某个因子。
     • 统计数组中所有是 $g_s$ 倍数的元素（即可构成子序列）。
     • 计算剩下元素的最大公因数 $g_{rest}$。
     • 计算 $\gcd(g_s + 1, g_{rest})$，更新答案。

---

代码解释

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

constexpr int MAX_VAL = 5000;

int gcd(int a, int b) {
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}
struct SegTree {
    int n;
    vector<int> tree;

    SegTree(const vector<int>& vals) {
        n = (int)vals.size();
        tree.assign(2 * n, 0);
        for (int i = 0; i < n; i++) {
            tree[n + i] = vals[i];
        }
        for (int i = n - 1; i > 0; i--) {
            tree[i] = gcd(tree[i << 1], tree[i << 1 | 1]);
        }
    }

    int query(int l, int r) const {
        int res = 0;
        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if ((l & 1) == 1) res = gcd(res, tree[l++]);
            if ((r & 1) == 0) res = gcd(res, tree[r--]);
        }
        return res;
    }
};

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

    int n;
    if (!(cin >> n)) return 0;
    if (n == 0) {
        cout << 1 << '\n';
        return 0;
    }

    vector<int> a(n);
    for (int& x : a) cin >> x;

    int g_initial = 0;
    for (int x : a) g_initial = gcd(g_initial, x);
    vector<int> counts(MAX_VAL + 1, 0);
    for (int x : a) counts[x]++;
    vector<int> gcd_of_multiples(MAX_VAL + 1, 0);
    for (int d = 1; d <= MAX_VAL; d++) {
        int g = 0;
        for (int m = d; m <= MAX_VAL; m += d) {
            if (counts[m] > 0) {
                g = gcd(g, m);
            }
        }
        gcd_of_multiples[d] = g;
    }
    vector<int> unique_vals;
    for (int i = 1; i <= MAX_VAL; i++) {
        if (counts[i] > 0) unique_vals.push_back(i);
    }
    int n_unique = (int)unique_vals.size();
    if (n_unique == 0) {
        cout << 1 << '\n';
        return 0;
    }
    unordered_map<int, int> val_to_idx;
    for (int i = 0; i < n_unique; i++) {
        val_to_idx[unique_vals[i]] = i;
    }
    SegTree seg(unique_vals);
    int max_ans = g_initial;
    for (int d = 1; d <= MAX_VAL; d++) {
        if (gcd_of_multiples[d] == d) {
            vector<int> bad_indices;
            for (int m = d; m <= MAX_VAL; m += d) {
                auto it = val_to_idx.find(m);
                if (it != val_to_idx.end()) {
                    bad_indices.push_back(it->second);
                }
            }
            int g_rest = 0;
            int last_idx = -1;
            for (int bad_idx : bad_indices) {
                if (bad_idx > last_idx + 1) {
                    g_rest = gcd(g_rest, seg.query(last_idx + 1, bad_idx - 1));
                }
                last_idx = bad_idx;
            }
            if (last_idx + 1 < n_unique) {
                g_rest = gcd(g_rest, seg.query(last_idx + 1, n_unique - 1));
            }

            int current_ans;
            if (g_rest == 0) {
                current_ans = d + 1;
            } else {
                current_ans = gcd(d + 1, g_rest);
            }
            max_ans = max(max_ans, current_ans);
        }
    }
    cout << max_ans << '\n';
    return 0;
}