带星号的表示 vp。

\(*\) CF Round 601 Div.1

B2. Send Boxes to Alice (Hard Version)

考虑 \(a\) 的前缀和数列 \(S\)，在 \(a\) 中移动一个数，相当于在 \(S\) 中单点 \(\pm 1\)。并且 \(S_n\) 一定是不变的，且最终的公约数一定是 \(S_n\) 的约数。显然只需要枚举所有质数 \(p\mid S_n\)。并且“所有 \(S_i\) 都是 \(p\) 的倍数”与“所有 \(a_i\) 都是 \(p\) 的倍数”是等价的。

所以，显然答案就是 \(\sum_{i=1}^{n-1} \min(S_i\bmod p,p-(S_i\bmod p))\)。

但最后还有一个问题：如何保证 \(S\) 单调不减？这个其实显然是可以保证的。