[ARC126C] Maximize GCD

设 \(a_x\) 为数列 \(a\) 中的最大值。

一般来说，与其处理 \(x | \gcd(A_1,\dots,A_N)\) ，处理 \(x = \gcd(A_1,\dots,A_N)\) 更加容易。这是因为后者能够被分解为各个元素：\(\forall i,x | A_i\)。

因此，我们将解决下面这个问题而不是原来的问题。

寻找 \(x\) 的最大值，这样就有可能在运算后得到 \(x | \gcd(A_1,\dots,A_N)\)。

假设 \(K\) 足够大，能够使得序列中每一个值都加到 \(a_{\max}\)，那我们就先把每个值都加到 \(a_{\max}\)，剩下的操作数再平均分配到每一个元素。

如果 \(K\) 不能使得序列中每一个值都加到 \(a_{\max}\)，我们能够发现，答案的最大值不超过 \(a_{\max}\)，也就是不超过 \(3 \times 10^5\)。

这个范围我们完全可以从大到小枚举 \(x\) 的值。

如何枚举 \(x\) 的值？

设 \(k\) 为一个整数，并且计算出对于所有 \(A_i\) 能够满足 \((k - 1)x < A_i \leq kx\) 的操作数。

我们可以计算出一个值域 \(\left(kx - x,kx \right]\) 内 \(A_i\) 的个数和 \(A_i\) 的和。由于是静态的，直接前缀和统计就可以。

这样枚举中找到满足需要的操作次数不大于 \(K\) 的 \(x\) 的最大值。