小欧的gcd

[题目链接](https://www.nowcoder.com/practice/68b4d34187ee41fab749b27d158f069f)

思路

把数组分成 段连续子数组，每段求和得到 ，要最大化 。

关键观察：答案一定是总和的因子

设总和为 。无论怎么分割，所有子数组的和加起来都等于 。如果 ，那么每个 都是 的倍数， 也必然是 的倍数。

所以答案一定是 的某个因子，我们只需要从大到小枚举 的因子 ，检查能否找到一种分割方式使得每段和都是 的倍数。

怎么检查因子 是否可行？

计算前缀和数组 。在位置 处切一刀，左边的和就是 。

如果 ，说明前 个元素的和是 的倍数。又因为 ，剩余部分的和 也是 的倍数。这样就至少分成了 2 段，每段和都是 的倍数，GCD 至少为 。

所以只要存在某个 使得 ，因子 就是可行的。从大到小枚举因子，第一个可行的就是答案。

复杂度

的因子个数为 级别，每个因子检查一遍前缀和是 ，总时间复杂度 ，其中 是因子个数。实际 远小于 ，完全够用。

代码

C++

[sol-C++]

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    vector<long long> a(n);
    for(int i=0;i<n;i++) scanf("%lld",&a[i]);
    long long S=0;
    for(int i=0;i<n;i++) S+=a[i];
    vector<long long> pre(n);
    pre[0]=a[0];
    for(int i=1;i<n;i++) pre[i]=pre[i-1]+a[i];
    long long absS = abs(S);
    if(absS==0){
        long long ans=0;
        for(int i=0;i<n-1;i++) ans=max(ans, abs(pre[i]));
        printf("%lld\n",ans);
        return 0;
    }
    vector<long long> divs;
    for(long long i=1;i*i<=absS;i++){
        if(absS%i==0){
            divs.push_back(i);
            if(i!=absS/i) divs.push_back(absS/i);
        }
    }
    sort(divs.rbegin(),divs.rend());
    for(long long d:divs){
        for(int i=0;i<n-1;i++){
            if(pre[i]%d==0){
                printf("%lld\n",d);
                return 0;
            }
        }
    }
    printf("1\n");
    return 0;
}

Java

[sol-Java]

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();
        long S = 0;
        for (int i = 0; i < n; i++) S += a[i];
        long[] pre = new long[n];
        pre[0] = a[0];
        for (int i = 1; i < n; i++) pre[i] = pre[i - 1] + a[i];
        long absS = Math.abs(S);
        if (absS == 0) {
            long ans = 0;
            for (int i = 0; i < n - 1; i++) ans = Math.max(ans, Math.abs(pre[i]));
            System.out.println(ans);
            return;
        }
        List<Long> divs = new ArrayList<>();
        for (long i = 1; i * i <= absS; i++) {
            if (absS % i == 0) {
                divs.add(i);
                if (i != absS / i) divs.add(absS / i);
            }
        }
        divs.sort(Collections.reverseOrder());
        for (long d : divs) {
            for (int i = 0; i < n - 1; i++) {
                if (pre[i] % d == 0) {
                    System.out.println(d);
                    return;
                }
            }
        }
        System.out.println(1);
    }
}

复杂度

• 时间复杂度：，其中 为 的因子个数
• 空间复杂度：