题解：AT_pakencamp_2020_day1_k Gcd of Sum

· · 题解

::::info[闲话] NOIP 模拟赛 T1。赛时饭堂了，没看出如何求划分为若干个和为 k 的倍数的子序列该怎么 O(n) 求，遂使用 O(n^2) 暴力 DP，喜提 TLE。 ::::

首先有一种想法是错误的，直接 DP 划分的最大公约数。这样状态转移的时候之前的最大公约数不一定是最优的，所以你需要记录之前的所有约数，然后你发现时间复杂度变成和 V 相关的了。

想到一个常用的技巧：假如一个值不容易计算，那么，枚举它。我们想想，到底有哪些数可能成为解呢？首先，假如这个数不是序列和的约数，那么肯定不能成为解，不然你怎么划分都不会划分出若干个它的倍数。这样问题就变得好做许多了，因为 1\sim 2\times10^{12} 中约数个数最多的数才六千多个。

然后注意到一件事情：假如可以划分出 k 段 x 的倍数，那么划分出 k-1 段 x 的倍数是肯定可行的，因为你可以合并相邻的两段。因此只需要求出每一个约数的最大划分段数即可。然后对于答案序列更新 1 到这个划分段数的每一个点。

然后就有一个经典结论了：序列前缀和模 x 等于 0 的数量就是划分段数，因为可以从每一个前缀和后面切开，而且这样一定是最优的。那么这一段时间复杂度为 O(n)。所以总时间复杂度 O(n\sigma(nV))，其中 \sigma(x) 表示 x 的约数个数。代码很好写。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2000 + 5;
int n, a[N], sum, pre[N], cq[N];

void solve(int x) {
    int cnt = 0;
    for(int i = 1; i <= n; i ++ ) if(pre[i] % x == 0) cnt ++ ;
    for(int i = cnt; i >= 1; i -- ) cq[i] = max(cq[i], x);
}

signed main() {
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        sum += a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    for(int i = 1; i * i <= sum; i ++ ) {
        if(sum % i == 0) {
            solve(i);
            solve(sum / i);
        }
    }
    for(int i = 1; i <= n; i ++ ) cout << cq[i] << endl;
    return 0; 
}