CF1780B GCD Partition

从 \(k\) 的角度出发，可以发现一定存在某种 \(k = 2\) 的划分方式，使得最终获得的分数最大。

为什么呢？

假定划分为 \(k = 3\) 时取得了最大分数，即 \(\gcd(b_1, b_2, b_3) = g\)。

设 \(b_1 = c_1g, b_2 = c_2g, b_3 = c_3g\)。则 \(\gcd(b_1 + b_2, b_3) = \gcd((c_1 + c_2)g, c_3g) \ge g\)。

而 \(g\) 是能获取到的最大分数，所以有 \(\gcd(b_1 + b_2, b_3) = \gcd(b_1, b_2, b_3) = g\)。

显然可以推广到任意的 \(k\)。

也就是说，对于任意取得最大分数的划分方式，都可以通过将多块并为一块的方式转化为 \(k = 2\) 的划分方式。

然后用前缀和加速区间求和，模拟所有 \(k = 2\) 的情况就好啦。

代码：

#include <bits/stdc++.h>

#define MAXN 200100

using namespace std;

typedef long long ll;

int T, n, maxa, a[MAXN];
ll sum[MAXN];

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            sum[i] = sum[i - 1] + a[i];
        }
        ll ans = 1;
        for (int i = 1; i < n; i++) ans = max(ans, __gcd(sum[i], sum[n] - sum[i]));
        printf("%lld\n", ans);
    }
}