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
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib>

using namespace std;

vector<pair<long long, int>> V;
vector<long long> V2;
vector<long long> V3, V4;

void gen(int id, long long cur){
    if(id == V.size()){
        V2.push_back(cur);
        return;
    }

    long long p = V[id].first;
    int cnt = V[id].second;
    long long val = 1;

    for(int i = 0; i <= cnt; i++){
        gen(id + 1, cur * val);
        val *= p;
    }
}

bool check(int k){
    int n = V3.size() - 1;
    int lim = n - k + 1;

    fill(V4.begin(), V4.end(), 0);

    for(int i = 1; i <= n; i++){
        long long cur = V3[i] - V3[i - 1];
        if(i > k){
            cur += V4[i - k];
        }
        if(i <= lim){
            if(cur < 0){
                return false;
            }
            V4[i] = cur;
        } else {
            if(cur != 0) {
                return false;
            }
        }
    }

    return true;
}

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

    int n;
    cin >> n;

    V3.assign(n + 1, 0);
    V4.assign(n + 1, 0);

    long long sum = 0;
    for(int i = 1; i <= n; i++){
        cin >> V3[i];
        sum += V3[i];
    }

    long long tmp = sum;
    for(long long p = 2; p <= tmp / p; p += (p == 2 ? 1 : 2)){
        if(tmp % p == 0){
            int cnt = 0;
            while(tmp % p == 0){
                tmp /= p;
                cnt++;
            }
            V.push_back({p, cnt});
        }
    }
    if(tmp > 1){
        V.push_back({tmp, 1});
    }

    gen(0, 1);
    sort(V2.rbegin(), V2.rend());

    for(auto k : V2){
        if(k > n){
            continue;
        }
        if(check((int)k)){
            cout << k;
            return 0;
        }
    }

    cout << 1;
    return 0;
}