题解

思路

把目标最大公约数改写为候选整数 $x$：只要能把每个 $A_i$ 增加到不小于它的最小 $x$ 的倍数，就能让最终最大公约数被 $x$ 整除。

做法

所需操作数为 $\operatorname{cost}(x)=\sum_i(\lceil A_i/x\rceil x-A_i)$。设 $V=\max A_i$。当 $x>V$ 时所有数都只能增加到 $x$，所以这部分的最优候选为 $\left\lfloor(\sum A_i+K)/N\right\rfloor$，且只需在它大于 $V$ 时计入答案。

对 $1\le x\le V$，按区间 $((q-1)x,qx]$ 汇总序列元素：区间内元素需要增加的总量是 $qx\cdot c-s$，其中 $c$ 和 $s$ 分别是元素个数与元素和。预处理值域上的计数前缀和与数值和前缀和后，每个区间可在 $O(1)$ 时间计算；枚举所有 $x$ 的区间总数是调和级数规模。若 $\operatorname{cost}(x)\le K$ 就用 $x$ 更新答案。

复杂度

总时间复杂度为 $O(N+V\log V)$，空间复杂度为 $O(V)$，所有和与费用均需使用 64 位整数。