codeforces #864 div2 B

GCD Partition

这道题首先要解决一个问题，要把区间分成几块，可以证明分成两块是更优

首先我们假设把区间分成了m（>= 2)块 b1, b2, b3, ...,bm,则答案是gcd(b1, b2, b3,..., bm),则b1，b2是 gcd(b1, b2, b3,..., bm)的倍数，那么b1 + b2也是gcd(b1, b2, b3,..., bm)的倍数，所以gcd(b1, b2, b3,..., bm)<=gcd(b1 + b2, b3,..., bm),所以依此类推，区间数越少，越优，所以k = 2是最优的

然后我们可以处理一个前缀和，枚举一下分段点，求一下gcd，找出最大值即可

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int a[N];
LL s[N];

LL gcd(LL a, LL b)
{
	if(b == 0)	return a;
	return gcd(b, a % b);
}

void solve()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; ++ i)	
	{
		scanf("%d", &a[i]);
		s[i] = s[i - 1] + a[i];
	}
	LL ans = 0;
	for(int i = 1; i <= n - 1; ++ i)
		ans = max(ans, gcd(s[i], s[n] - s[i]));
	cout << ans << endl;
}

int main()
{
	int t;
	cin >> t;
	while(t --)	solve();
}