[ARC126C] Maximize GCD 题解-526互联

题意

给定一个序列 \(A\)，每次操作可以使 \(A_i + 1\)（\(i \in \left[1, n\right]\)，\(K\) 次操作的 \(i\) 可以不同），最多可以做 \(K\) 次。问 \(\gcd{A_1, A_2, ..., A_n}\) 的最大值。

题解

首先，如果 \(K\) 可以把当前序列中所有的数都加到 \(A_{\max}\)，那就全部加到 \(A_{\max}\)，在此基础上同步对所有数相加即可。

如果 \(K\) 不足以把当前序列中所有的数都加到 \(A_{\max}\)，那么可以发现最后的答案 \(Ans \le A_{\max}\)，因为 \(A_{\max} \le 3 \times 10^5\)，所以可以直接枚举判断当前答案是否成立。

可以把原题的条件进行转化

\[\gcd{A_1, A_2, ..., A_n} = Ans \Rightarrow Ans \mid {A_1, A_2, ..., A_n} \]

又因为题目要求的是最大值，所以从大到小枚举即可。接下来考虑如何判定。

设当前枚举的答案是 \(x\)，那么对于序列中的数 \(A_i\)，它应当被加到 \(kx \ge A_i\)，考虑枚举 \(k\) 进行判定，使用前缀和记录序列中一定值域中的数的个数和和即可求解。

设 \(M = A_{\max}\)，则最终的复杂度为 \(\mathcal{O}(N + M \times \sum\limits_{i = 1}^{M} \dfrac{1}{i}) = \mathcal{O}(N + M \log M)\)。

Code

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;

class TreeArray {
public:
    typedef ValueVector container;
private:
    valueType size;
    container data;

    static valueType lowBit(valueType x) {
        return x & -x;
    }

public:
    explicit TreeArray(valueType n) : size(n), data(size + 1, 0) {};

    void insert(valueType pos, valueType key) {
        while (pos < size) {
            data[pos] += key;

            pos += lowBit(pos);
        }
    }

    valueType sum(valueType pos) const {
        valueType result = 0;

        while (pos > 0) {
            result += data[pos];

            pos -= lowBit(pos);
        }

        return result;
    }
};

constexpr valueType \maxA = 6e5 + 5;

int main() {
    std::ios_base::sync_with_stdio(false);

    valueType N, K;

    std::cin >> N >> K;

    if (N == 1) {
        valueType A;

        std::cin >> A;

        std::cout << (A + K) << std::endl;

        return 0;
    }

    ValueVector source(N);

    for (auto &iter: source)
        std::cin >> iter;

    TreeArray sum(\maxA), count(\maxA);

    valueType \max = 0;

    for (auto const &iter: source) {
        \max = std::\max(\max, iter);

        sum.insert(iter, iter);
        count.insert(iter, 1);
    }

    typedef std::function<bool(valueType)> CheckFunction;

    CheckFunction check = [\max, &sum, &count, K](valueType n) -> bool {
        valueType result = 0;

        for (valueType i = n; i <= \max + n; i += n)
            result += i * (count.sum(i) - count.sum(i - n)) - (sum.sum(i) - sum.sum(i - n));

        return result <= K;
    };

    valueType const minK = N * \max - sum.sum(\max);

    if (K >= minK) {
        std::cout << (\max + (K - minK) / N) << std::endl;
    } else {
        for (valueType i = \max; i >= 1; --i) {
            if (check(i)) {
                std::cout << i << std::endl;

                return 0;
            }
        }
    }
    return 0;
}

maximize 126c arc gcd