Codeforces Round #846 (Div. 2) B. GCD Partition

B. GCD Partition

参考题解链接 : Codeforces Round #846 (Div. 2) — Tutorial - Codeforces

题意 : 给一个长度为 n 的序列, 并将其分成连续的 k 块(k > 1), 得到序列 b, 使得 \(gcd(b_{1}, b_{2}, b_{3}, ..., b_{k} )\) 的值最大

思路 : 当 k = m 时, 就能得到序列: \(b_{1}, b_{2}, b_{3}, ..., b_{m}\). 因为 \(b_{1}\) 和 \(b_{2}\) 都是 \(gcd(b_{1}, b_{2}, b_{3}, ..., b_{m} )\) 的公约数, 那么可得 \(b_{1} + b_{2}\) 也是 \(gcd(b_{1}, b_{2}, b_{3}, ..., b_{m} )\) 的公约数, 所以有 \(gcd(b_{1}, b_{2}, b_{3}, ..., b_{m} ) \le gcd(b_{1}+ b_{2}, b_{3}, ..., b_{m} )\).

以此类推, 当 k = 2 时, 和 k 等于其他数(也就是分大于两块的情况), 答案不会受到影响, 那么就可以暴力枚举分成两份的情况

代码

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

typedef long long LL;
const int N = 2e5 + 10;
int a[N];

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        scanf("%d", &n);
        LL sum = 0;
        for (int i = 0; i < n; i++) scanf("%d", &a[i]), sum += a[i];

        LL ans = 1, cur = 0;
        for (int i = 0; i < n - 1; i++) {
            cur += a[i], sum -= a[i];
            ans = max(ans, __gcd(cur, sum));
        }

        printf("%lld\n", ans);
    }

    return 0;
}