C - Maximize GCD Editorial by evima
Let \(A_{\max}\) denote \(\max\{A_1, \ldots, A_N\}\).
◆ Rephrasing the problem
Generally speaking, rather than to deal with the condition \(x \mid \gcd(A_1, \ldots, A_N)\), it is easier to deal with the condition \(x = \gcd(A_1, \ldots, A_N)\). This is because the latter can be decomposed into conditions on respective elements: \(\forall i, x\mid A_i\).
Therefore, we will solve the following problem instead of the original.
Find the maximum value of \(x\) such that it is possible to end up with \(x\mid \gcd(A_1, \ldots, A_N)\) being satisfied after operations.
We can easily see that rephrasing the problem in this way does not change the answer.
Let \(\text{cost}(x)\) denote the minimum number of operations needed to satisfy \(x\mid \gcd(A_1, \ldots, A_N)\), that is, make every \(A_i\) divisible by \(x\).
◆ Computing \(\text{cost}(x)\)
\(\text{cost}(x)\) is the sum of numbers of operations needed to make respective \(A_i\) divisible of \(x\).
Let \(k\) be an integer and compute the number of operations for all \(A_i\) such that \((k-1)x < A_i \leqq kx\) at once. For \(A_i\) in this range, we need \(kx - A_i\) operations, for a total of \(\sum_i (kx - A_i) = \sum_i kx - \sum_i A_i\). That is, we can see that the total number of operations for \(A_i\) in this range is \(kxc - s\), where:
- \(c\) is the number of indices \(i\) such that \((k-1)x < A_i \leq kx\), and
- \(s\) is the sum of \(A_i\) over all \(i\) such that \((k-1)x < A_i \leq kx\).
This number can be computed in \(O(1)\) time by computing prefix sums beforehand.
By shifting \(k\) and add up these sums, we can compute \(\text{cost}(x)\) in \(O(\lceil A_{\max} / x\rceil)\) time.
◆ The whole solution
First, we perform the computation of \(\text{cost}(x)\) stated above for \(1\leqq x\leqq A_{\max}\). It takes \(O(N + A_{\max})\) time to pre-compute prefix sums, and \(O(\sum_{1\leq x\leq A_{\max}}\lceil A_{\max} / x\rceil)\) time in total to compute \(\text{cost}(x)\). Since \(\sum_{1\leq x\leq A_{\max}}\lceil A_{\max} / x\rceil = O(A_{\max}\log A_{\max})\), the computations so far takes a total of \(O(N + A_{\max}\log A_{\max})\) time.
So far, we have determined for all \(x\) in the range \(x \leqq A_{\max}\) whether it is possible to make every \(A_i\) divisible of \(x\). What remains is the case \(x > A_{\max}\). Since \(\text{cost}(x) = Nx - \sum_i A_i\) holds in this case, it is easy to determine whether there exists \(x\) such that \(\text{cost}(x)\leqq K\) and find the maximum value of \(x\) if it exists.
Therefore, the problem can be solved in a total of \(O(N + A_{\max}\log A_{\max})\) time.
◆ Sample Implementations
posted:
last update: