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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>

using namespace std;

vector<int> allFactors(long long s, long long n) {
	vector<int> factors;
	for (long long i = 2LL; i <= n; i++) {
		if (s % i == 0LL) {
			factors.push_back((int) i);
		}
	}
	
	return factors;
}

bool isPossible(const vector<long long>& a, int k) {
	int n = a.size();
	
	vector<long long> drop(n, 0);
	
	long long curr = 0LL;
	
	for (int i = 0; i < n; i++) {
		curr -= drop[i];
		long long added = a[i] - curr;
		
		if (added < 0LL) {
			return false;
		}
		
		curr += added;
		
		if (i + k < n) {
			drop[i+k] = added;
		} else if (i + k > n) {
			if (added > 0LL) {
				return false;
			}
		} else if (i + k == n) {
			if (a[n-1] != added) {
				return false;
			}
		}
	}
	
	return (curr == a[n-1]);
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	
	int n;
	cin >> n;
	vector<long long> a(n);
	vector<bool> pos(n+1, true);
	
	long long sum = 0LL;
	
	for (int i = 0; i < n; i++) {
		long long ai;
		cin >> ai;
		a[i] = ai;
		sum += ai;
	}
	
	vector<int> factors = allFactors(sum, n);
	
	for (int i = 0; i < factors.size(); i++) {
		int num = factors[i];
		
		if (!pos[num]) {
			continue;
		}
		
		bool possible = isPossible(a, num);
		
		if (!possible) {
			for (int j = num; j <= n; j += num) {
				pos[j] = false;
			}
		}
	}
	
	int result = 1;
	
	for (int i = factors.size() - 1; i >= 0; i--) {
		if (pos[factors[i]]) {
			result = factors[i];
			break;
		}
	}
	
	cout << result;
}