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
fn main() {
    let mut lines = std::io::stdin().lines().map(|x| x.unwrap());
    let n = lines.next().unwrap().parse::<usize>().unwrap();
    let a = lines
        .next()
        .unwrap()
        .split_whitespace()
        .map(|x| x.parse::<i64>().unwrap())
        .collect::<Vec<_>>();

    let mut is_prime = vec![true; n + 1];
    let mut primes = vec![];
    for i in 2..=(n.isqrt()) {
        if is_prime[i] {
            primes.push(i as i64);
            for k in 2..=(n / i) {
                is_prime[i * k] = false;
            }
        }
    }
    for i in (n.isqrt() + 1)..=n {
        if is_prime[i] {
            primes.push(i as i64);
        }
    }
    // eprintln!("{:?}", primes);

    let mut best = 1;
    go(&a, &primes, 1, &mut best);
    println!("{}", best);
}

fn go(a: &[i64], primes: &[i64], current: i64, best: &mut i64) {
    if *best < current {
        *best = current;
    }

    if primes.is_empty() {
        return;
    }

    let prime = primes[0];
    if current * prime > a.len() as i64 {
        return;
    }

    // eprintln!("curr{} p{} a{:?}", current, prime, a);
    let mut scratch = a.to_owned();
    let mut success = true;
    'bust: for i in 0..scratch.len() {
        if scratch[i] > 0 {
            if i + ((prime - 1) * current) as usize >= scratch.len() {
                success = false;
                break 'bust;
            }
            for j in 1..prime {
                if scratch[i + (j * current) as usize] < scratch[i] {
                    success = false;
                    break 'bust;
                } else {
                    scratch[i + (j * current) as usize] -= scratch[i];
                }
            }
        }
    }

    if success {
        go(&scratch, primes, current * prime, best);
    }
    go(a, &primes[1..], current, best);
}