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
#include <cstdio>
#include <algorithm>

using namespace std;

#define MAX (100100)
typedef long long I;

int a[MAX], f[MAX];

int n,k;

bool test(int k) {
    int b=0,p;
    for(int i=0;i<=n;i++) f[i] = 0;
    for(int i=0;i<=n;i++) {
//            p=max(a[i]-b,0);
  //      printf("%d b:%d a:%d p:%d\n",i,b,a[i],p);
            b-=f[i];
        if(a[i]-b < 0) return false;
        else {
            p=max(a[i]-b,0);
            b+=p;
            if(i+k <= n) f[i+k]+=p;
           // printf("f[%d]: %d\n", i+k,f[i+k])
        }
    }
    return true;
}

I S;

int  main() {
    
    scanf("%d", &n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<n;i++) S+=a[i];

    for(k=n;k>1;k--) {
//        printf("k:%d S:%lld\n",k,S);
        if((S%k)==0 && test(k)) {
            break;
        }
    }
    printf("%d\n",k);
}