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
109
110
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int const max_P = 4000000;
bool sieve[max_P];
vector<long long> primes;

void calculate_primes() {
    primes = vector<long long>();
    for (int i = 0; i < max_P; i++) {
        sieve[i] = false;
    }
    for (int i = 2; i < max_P; i++) {
        if (!sieve[i]) {
            primes.push_back(i);
            for (int j = i; j < max_P; j += i) {
                sieve[j] = true;
            }
        }
    }
}
int cases;
int n;
int const max_N = 1000002;
int count_bur[max_N];
int count_changes[max_N];

bool check(int k) {
    int cur_count = 0;

    for (int i = 0; i < n; i++) {
        count_changes[i] = 0;
    }

    for (int i = 0; i < n - k + 1; i++) {
        cur_count += count_changes[i];
        if (cur_count > count_bur[i]) {
            return false;
        }
        // count_bur[i] <= cur_count
        count_changes[i + k] = -(count_bur[i] - cur_count);
        cur_count = count_bur[i];
    }
    for (int i = n - k + 1; i < n + 1; i++) {
        cur_count += count_changes[i];
        if (cur_count != count_bur[i]) {
            return false;
        }
    }
    return true;
}
vector<long long> all_divisors;
vector<pair< int, long long >> prime_factors;

void calculate_divisors(long long prev, int i) {
    // iterate over powers of a give base
    if (i >= prime_factors.size()) 
    {
        all_divisors.push_back(prev);
        return;
    }
    auto x = prime_factors[i];
    long long p = x.second;
    long long factor = 1;
    for (int power = 0; power <= x.first; power++) {
        calculate_divisors(prev*factor, i+1);
        factor *= p;
    }
}

int main()
{
    calculate_primes();
    cin >> n;
    long long total_sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> count_bur[i];
        total_sum += count_bur[i];
    }
    count_bur[n] = 0;

    prime_factors = vector<pair<int,long long>>();
    for (auto p : primes) {
        if (total_sum % p == 0) {
            int power = 0;
            while (total_sum % p == 0) {
                total_sum /= p;
                power++;
            }
            prime_factors.push_back({ power,p });
            continue;
        }
    }
    if (total_sum > 1) {
        prime_factors.push_back({ 1,total_sum }); //
    }
    calculate_divisors(1, 0);
    sort(begin(all_divisors), end(all_divisors));
    // ROZPATRZ PRZYPADEK GDY SUMA JEST LICZBĄ PIERWSZĄ.
    
    int best_k = 1;
    for (auto d : all_divisors) {
        if (d <= n && check(d)) {
            best_k = d;
        }
    }
    cout << best_k;

}