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

using namespace std;

bool f(int k, vector<int> v) {
    int n;
    n = v.size();
    vector<int> w;
    for(int i=0; i<n; ++i) w.push_back(0);
    bool cz = true;
    w[0] = v[0];
    long long s = 0,ind,p;
    for(int i=1; i<n; ++i) {
        if(i < min(k,n-k+1)) {
            w[i] = v[i] - v[i-1]; if(w[i] < 0) return false;
        }
        else if(i < n - k + 1) {
            w[i] = v[i] - v[i-1] + w[i-k]; if(w[i] < 0) return false;
        }
        else {
            ind = i - min(i,k-1); p = i; break;
            //if(i-min(i,k-1)-1 >= 0) s -= w[i-min(i,k-1)-1];
            //for(int j=i-min(i,k-1); j<=n-k ; ++j) s += w[j]; /////////?????????????
            //if(v[i] != s) cz = false;
        }
    }
    for(int j=ind; j<=n-k; ++j) s += w[j];
    if(v[p] != s) cz = false;
    for(int i=p+1; i<n; ++i) {
        if(i-min(i,k-1)-1 >= 0) s -= w[i-min(i,k-1)-1];
        if(v[i] != s) cz = false;
    }
    return cz;
}

int main() {
    int n,a;
    long long S = 0;
    vector<int> v;
    cin>>n;
    for(int i=0; i<n; ++i) {
        cin>>a;
        v.push_back(a);
        S += a;
    }
    //for(int i=1; i<=n; ++i) cout<<f(i,v)<<endl;
    vector<int> D;
    vector<bool> cz,ans;
    for(int i=2; i<=n; ++i) {
        if(S % i == 0) {
            D.push_back(i);
            cz.push_back(true);
            ans.push_back(true);
        }
    }
    int k; k = D.size();
    if(k == 0) {
        cout<<1;
        return 0;
    }
    srand(time(0));
    int l;
    while(true) {
        l = rand() % k;
        while(cz[l] == false) l = (l+1) % k;
        if(f(D[l],v) == true) {
            for(int i=0; i<k; ++i) if(D[l] % D[i] == 0) {
                cz[i] = false;
                ans[i] = true;
            }
        }
        else {
            for(int i=0; i<k; ++i) if(D[i] % D[l] == 0) {
                cz[i] = false;
                ans[i] = false;
            }
        }
        bool cz2 = true;
        for(int i=0; i<k; ++i) if(cz[i] == true) cz2 = false;
        if(cz2) break;
    }
    int Max = 1;
    for(int i=0; i<k; ++i) if(ans[i]) Max = max(Max,D[i]);
    cout<<Max;
    
    
    
    
    
    
    
    
    
    return 0;
}