AT_pakencamp_2020_day1_k Gcd of Sum题解

zpy12345 · 2026-07-25 19:14:33 · 题解

我们可以发现几个简单的小性质：

1. 最终的答案一定是 \sum_{i=1}^{N} A_i 的约数。
2. 假设最后的答案是 g，我们先对 A 做一下前缀和 s，由于答案要划分成若干连续子序列，所以一定存在若干个 i 使得 g|s_i，这些位置都是可以作为划分点的。显然，如果存在 k 个划分点，则我们可以将序列划分至多 k+1 份，少于 k+1 份也一定是可以划分出来的。

于是我们枚举 \sum_{i=1}^{N} A_i 的约数 g，对于每个约数扫一遍序列求出划分点的数量 k，对于 1 到 k 的答案全部对 g 取 \max 即可。

时间复杂度 O(\sqrt{M} N)，其中 M=\sum_{i=1}^{N} A_i。不过显然 M 的约数不会很多，这个是跑不满的。