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
#include <bits/stdc++.h>
#define nl '\n'

using namespace std;
using ll = long long;

bool check(vector<ll> nums, int n, ll d){
    ll sum = 0;
    queue<pair<ll,ll>> timeline;
    for(int i=0; i<n; i++){
        while(timeline.size() && timeline.front().first <= i){ 
            sum -= timeline.front().second;
            timeline.pop();
        }
        nums[i] -= sum;
        if(nums[i] < 0) return false;
        timeline.push({i+d, nums[i]});
        sum += nums[i];
    }
    while(timeline.size() && timeline.front().first <= n){ 
        sum -= timeline.front().second;
        timeline.pop();
    }
    if(sum == 0) return true;
    else return false;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin>>n;
    ll sum = 0;
    vector<ll> nums(n);
    for(auto &i: nums){ cin>>i; sum += i; }
    vector<ll> prime_factors;
    unordered_map<int, vector<int>> G;
    //cerr<<sum<<nl;
    ll sum2 = sum;
    for(ll i = 2; i*i <= sum2; i++){
        if(sum2 % i == 0){
            prime_factors.push_back(i);
            while(sum2 % i == 0){ sum2 /= i; }
        }
    }
    prime_factors.push_back(sum);
    for(int i=2; i<=n; i++){
        if(sum % i == 0){
            G[i] = {};
        }
    }
    int res = 1;
    for(auto [a, b]: G){
        if(check(nums, n, a)){
            res = max(res, a);
        }
    }
    cout<<res<<nl;
    return 0;
}