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
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
#include <bits/stdc++.h>
using namespace std;

const int INPUT_SIZE = 100010;

long long ambers[100010];

int prime_factors[40]; // Will be much less
int powers[40];
int current[40];
int primes_count = 0;

long long decrease_steps[2 * 100010];

int n;

// Before passing input, CHECK IF SMALL ENOUGH!
bool check_correctness(int width) {
	for (int i = 0; i <= n; i++) {
		decrease_steps[i] = 0;
	}

	long long sum = 0;
	for (int i = 0; i <= n; i++) {
		sum += decrease_steps[i];
		if (sum > ambers[i]) {
			return false;
		}
		// Avoids an if, but doesnt exit immediately - maybe faster?
		decrease_steps[i + width] += (sum - ambers[i]);
		sum = ambers[i];
	}
	return true;
}

void factorise(long long x) {
	for (long long i = 2; i*i <= x; i++) {
		if (x % i == 0) {
			prime_factors[primes_count] = i;
			while (x % i == 0) {
				x /= i;
				powers[primes_count]++;
			}
			primes_count++;
		}
	}
	if (x != 1) {
		prime_factors[primes_count] = x;
		powers[primes_count] = 1;
		primes_count++;
	}
}

long long get_value() {
	long long res = 1;
	for (int i = 0; i < primes_count; i++) {
		res *= pow(prime_factors[i], current[i]);
	}
	return res;
}

bool get_next() {
	bool carry = true;
	for (int i = 0; i < primes_count && carry; i++) {
		current[i] += 1;
		if (current[i] > powers[i]) {
			current[i] = 0;
		}
		else {
			carry = false;
		}
	}
	return !carry;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n;
	long long sum = 0;

	for (int i = 0; i < n; i++) {
		cin >> ambers[i];
		sum += ambers[i];
	}
	
	factorise(sum);

	int max = 1;

	do {
		long long l_factor = get_value();
		//cout << "Checking factor " << l_factor << "\n";
		if (l_factor > (long long)n) {
			continue;
		}
		int factor = (int) l_factor;
		if (factor > max) {
			//cout << "Better than max!\n";
			if (check_correctness(factor)) {
				max = factor;
			}
		}

	} while (get_next());
	cout << max;
}