526互联

CF803C Maximal GCD 题解

发布时间 2023-08-17 19:24:31作者: User-Unauthorized

题意

构造一个长度为 \(k\)，和为 \(n\) 的严格单调递增序列，并最大化其最大公约数。

（\(1 \le n,k \le 10^{10}\)）

题解

首先可以发现一个事实，这个序列的最大公约数一定为 \(n\) 的因子。所以我们可以考虑枚举 \(n\) 的所有因子并判断其能否成为整个序列的最大公约数。假设我们现在枚举到的因子为 \(x\)，那么满足要求的序列各个元素一定为 \(x\) 的倍数，考虑最终序列 \(a_i\) 除 \(x\) 后的值 \(b_i\)，显然 \(b\) 同 \(a\) 一样单调递增。

考虑一个引理，长度为 \(k\) 的严格单调递增序列的和最小为 \(\dfrac{k \left(k + 1\right)}{2}\)，并且一定存在和大于 \(\dfrac{k \left(k + 1\right)}{2}\) 的长度为 \(k\) 的严格单调递增序列。证明考虑从和最小的序列情况下改变序列的几个值，使得和增加 \(\Delta sum - \dfrac{k \left(k + 1\right)}{2}\)，显然直接将最后一位的值增加该差值即可满足要求，即 \(b_k \leftarrow b_k + \Delta\)。

所以我们以 \(\mathcal{O}(\sqrt{n})\) 的复杂度枚举 \(n\) 的各个因子 \(d\)，并找到最大的满足 \(n / d \ge \dfrac{k \left(k + 1\right)}{2}\) 的因子 \(D\)，设 \(\Delta = n - d \times \dfrac{k \left(k + 1\right)}{2}\)，那么最终序列的前 \(k - 1\) 项依次为 \(1 \cdot D, 2 \cdot D, \cdots, \left(k - 1\right) \cdot D\)，第 \(k\) 项为 \(k \cdot D + \Delta\)。可以证明这样的序列一定合法且序列的最终长度不会超过 \(\max(k, \dfrac{n}{\dfrac{k \left(k + 1\right)}{2}})\)。

Code

//Codeforces - CF803C
#include <bits/stdc++.h>

typedef long long valueType;

int main() {
    valueType N, K;

    std::cin >> N >> K;

    if (N / K < (K - 10) / 2) {
        std::cout << -1 << std::endl;

        return 0;
    }

    if (N < K * (K + 1) / 2) {
        std::cout << -1 << std::endl;

        return 0;
    }

    valueType const min = K * (K + 1) / 2;
    valueType const start = std::ceil(std::sqrt((long double) N) + 10);

    valueType result = 1;

    for(valueType i = start; i >= 1; --i) {
        if (N % i == 0) {
            if (N / i >= min)
                result = std::max(result, i);

            if (i >= min)
                result = std::max(result, N / i);
        }
    }

    valueType const remain = N / result - min;

    for(valueType i = 1; i < K; ++i)
        std::cout << i * result << ' ';

    std::cout << result * (K + remain) << std::endl;

    return 0;
}