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
//Solution by Mikołaj Kołek

#include "bits/stdc++.h"
#define intin *istream_iterator<int>(cin)

using namespace std;

unordered_map<long long, int> factor(long long num) {
	unordered_map<long long, int> factors;
	
    for(long long i = 2; i * i <= num and num != 1; i++) {
        while(num % i == 0) {
            num /= i;
			factors[i]++;
        }
    }
 
    if(num != 1)
        factors[num]++;
 
    return factors;
}

vector<long long> divisors(long long num) {
	auto factors = factor(num);
	vector<long long> divs;
	
	function<void(long long)> findAllDivisors = [&] (long long a) {
		if(factors.empty()) {
			divs.push_back(a);
			return;
		}

		auto [key, val] = *factors.begin();
		factors.erase(key);

		for(int i = 0; i <= val; i++) {
			findAllDivisors(a);
			a *= key;
		}

		factors[key] = val;
	};
	findAllDivisors(1);
	
	return divs;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n = intin;
	long long aSum = 0;
	vector<int> a(n);
	for(auto &el : a) {
		cin >> el;
		aSum += el;
	}
	
	long long res = 1;
	auto divs = divisors(aSum);
	for(auto &el : divs) {
		if(el > n)
			continue;
		
		bool possible = true;
		deque<long long> waves;
		long long currentSum = 0;
		for(int i = 0; i < n; i++) {
			if(currentSum > a[i] or (i > (n - el) and currentSum != a[i])) {
				possible = false;
				break;
			}
			
			waves.push_back(a[i] - currentSum);
			currentSum = a[i];
			if(waves.size() >= el) {
				currentSum -= waves.front();
				waves.pop_front();
			}
		}
		
		if(possible)
			res = max(res, el);
	}
	
	cout << res;
	
	return 0;
}