最大公约数2（gcd）

一个环，第 $i$ 个数字为 $a_i$，求对于 $k=1\sim n$ ，求将环分为 $k$ 端后，每一段数字和的 $\gcd$ 的最大值。

$n\le 2000,a_i\le 5\times 10^7$ 。

首先看到 $\gcd$ 和 $\max$ ，我们应该立马想到：枚举 $\gcd=g$。

那么此时，对于一个 $k$，问题就变为了是否存在一种划分使得每一段都为 $g$ 的倍数。

接下来，显然的，考虑前缀和。设 $s_i=\sum_{j=1}^ia_j$ ，那么一段 $[i+1,j]$ 的和为 $g$ 的倍数，就变为 $s_i\equiv s_j\pmod g$ 了。然后，由于是环，问题转变为是否存在 $k$ 个数，使得他们的 $s$ 模 $g$ 同余。

这个问题如果直接枚举 $g$ ,可以做到复杂度 $\mathcal{O}(n\sum a_i)$ ，可以获得 $50\%$ 的分数。

然后，一个关键观察： $g\mid s_n$ 。

这样，我们只需要枚举 $s_n$ 的因数即可。由于 $s_n\le 10^{11},d(s_n)\le 5\times 10^3$，这样我们只需要枚举 $5\times 10^3$ 个 $g$ 就行。复杂度 $\mathcal{O}(nd(s_n))$。