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
101
102
103
104
105
106
107
108
109
110
111
112
113
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;

typedef unsigned long long ull;
ull modmul(ull a, ull b, ull M) {
	ll ret = a * b - M * ull(1.L / M * a * b);
	return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
ull modpow(ull b, ull e, ull mod) {
	ull ans = 1;
	for (; e; b = modmul(b, b, mod), e /= 2)
		if (e & 1) ans = modmul(ans, b, mod);
	return ans;
}

bool isPrime(ull n) {
	if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
	ull A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022},
	    s = __builtin_ctzll(n-1), d = n >> s;
	for (ull a : A) {   // ^ count trailing zeroes
		ull p = modpow(a%n, d, n), i = s;
		while (p != 1 && p != n - 1 && a % n && i--)
			p = modmul(p, p, n);
		if (p != n-1 && i != s) return 0;
	}
	return 1;
}

ull pollard(ull n) {
	ull x = 0, y = 0, t = 30, prd = 2, i = 1, q;
	auto f = [&](ull x) { return modmul(x, x, n) + i; };
	while (t++ % 40 || __gcd(prd, n) == 1) {
		if (x == y) x = ++i, y = f(x);
		if ((q = modmul(prd, max(x,y) - min(x,y), n))) prd = q;
		x = f(x), y = f(f(y));
	}
	return __gcd(prd, n);
}
vector<ull> factor(ull n) {
	if (n == 1) return {};
	if (isPrime(n)) return {n};
	ull x = pollard(n);
	auto l = factor(x), r = factor(n / x);
	l.insert(l.end(), all(r));
	return l;
}

vector<pair<ll,int>> roots (ll n){
    auto ret = factor(n);
    map<ll,int> cnt;
    for(auto c : ret) cnt[c]++;
    vector<pair<ll,int>> ans(all(cnt));
    return ans;
}

const int mxN = 1e5+67;

int a[mxN], dp[mxN];

int main(){
    cin.tie(NULL),ios::sync_with_stdio(false);
    
    int n; cin >> n;
    rep(i,0,n) cin >> a[i];

    ll sm = accumulate(a, a+n, 0ll);

    auto pfacts = roots(sm);

    vector<ll> divs = {1};
    for(auto [k,v] : pfacts) {
        int s = sz(divs);
        rep(i,0,v) {
            rep(j,0,s) divs.push_back(divs.end()[-s] * k);
        }
    }

    ll ans = 1;
    for (int i = n-2; i >= 0; --i) {
        a[i+1] -= a[i];
    }

    for(auto d : divs) if (d <= n and d > ans) {
        memcpy(dp,a,4*n);
        bool good = 1;
        rep(i,0,n - d) {
            if (dp[i] < 0) {
                good = 0;
                break;
            }
            dp[i+d] += dp[i];
            dp[i] = 0;
            dp[i+1] += dp[i];
        } if (good) {
            rep(i,n-d+1,n) if (dp[i]){
                good = 0;
                break;
            }
        }
        if (good) {
            ans = d;
        }
    }

    cout << ans << '\n';
}