1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool ok(ll k, ll n, const vector<ll> &a) {
	vector<ll> x(n + 1, 0);
	ll pA = 0;

	for (ll i = 1; i <= n; ++i) {
		ll A = a[i - 1];
		ll xi = A - pA + (i > k ? x[i - k] : 0);

		if (xi < 0 || (xi > 0 && i > n - k + 1))
			return false;

		x[i] = xi;
		pA = A;
	}

	return true;
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);

	ll n;
	cin >> n;

	vector<ll> a(n);
	ll suma = 0, waz = 0;
	for (ll i = 0; i < n; ++i) {
		cin >> a[i];
		suma += a[i];
		waz += (i + 1) * a[i];
	}

	ll G = gcd(suma, 2 * waz + suma);

	vector<ll> v;
	for (ll k = 1; k * k <= G; ++k) {
		if (G % k == 0) {
			if (k <= n)
				v.push_back(k);
			if (G / k <= n)
				v.push_back(G / k);
		}
	}

	sort(v.begin(), v.end(), greater<ll>());

	for (ll k : v)
		if (ok(k, n, a)) {
			cout << k << '\n';
			return 0;
		}
}