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
#include <iostream>

const int base = 1 << 18;
int c[base];
bool vis[base];
int pref[base];

namespace FastIO {
    const int S = 1 << 20;
    char buf[S];
    int pos = 0, len = 0;

    inline char getChar() {
        if (pos == len) {
            pos = 0;
            len = fread(buf, 1, S, stdin);
            if (!len) return EOF;
        }
        return buf[pos++];
    }

    inline int readInt() {
        int x = 0, neg = 0;
        char c = getChar();

        while (c < '0' || c > '9') {
            if (c == '-') neg = 1;
            c = getChar();
        }

        while (c >= '0' && c <= '9') {
            x = x * 10 + (c - '0');
            c = getChar();
        }

        return neg ? -x : x;
    }
}

bool solve(int k, int n){
    int i = 1; bool is_good = true;
    for(; i <= n - k + 1; i++){
        pref[i] += pref[i - 1];
        int temp = c[i] - pref[i];
        if(temp < 0) {is_good = false; break;};

        pref[i] += temp;
        pref[i + k] -= temp;
    }
    for(; i <= n; i++){
        pref[i] += pref[i - 1];
        if(c[i] != pref[i]) {is_good = false; break;}
    }

    for(int j = 0; j <= i + k + 7; j++) pref[j] = 0;
    return is_good;
}

int main(){
    int n = FastIO::readInt();
    for(int i = 1; i <= n; i++) c[i] = FastIO::readInt();

    int res = 1;
    for(int i = 2; i <= n; i++){
        if(vis[i] == true) continue;
        bool temp = solve(i, n);
        if(temp == true) res = i;
        else{
            for(int j = i; j <= n; j += i)
                vis[j] = true;
        }
    }

    std::cout << res;
    return 0;
}