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
#include <bits/stdc++.h>
using namespace std;

#define ll long long


const int MAX_N = 100000;

int n, a[MAX_N + 1], res;
ll sum;
int sums[MAX_N + 1];

vector<int> divisors;


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

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

  for(ll i = 1; i * i <= sum; i++) {
    if (sum % i == 0) {
      ll divisor1 = i;
      ll divisor2 = sum / i;
      if(divisor1 <= n) {
        divisors.push_back(divisor1);
      }
      if(divisor2 <= n && divisor1 != divisor2) {
        divisors.push_back(divisor2);
      }
    }
  }

  sort(divisors.begin(), divisors.end());

  for(int d : divisors) {
    int current_sum = 0;
    bool can = true;
    for(int i = 1; i <= n; i++) {
      if(i - d >= 1) {
        current_sum -= sums[i - d];
      }
      int val = a[i] - current_sum;
      if(val < 0) {
        can = false;
        break;
      }
      if (n - d + 1 < i && val != 0) {
        can = false;
        break;
      }
      sums[i] = val;
      current_sum += val;
    }
    if(can) {
      res=d;
    }
  }

  cout << res << endl;
}