ARC126 C - Maximize GCD - かんプリンの学習記録

問題概要
解説
提出プログラム
感想

問題概要

長さ ${N}$ の数列 ${A}$ が与えられる．この数列の要素を一つ選び ${1}$ を加えるという操作を ${K}$ 回まで行うことができるとき， ${A}$ の全要素のgcdの最大値を求めよ．

${2\leq N\leq 3×10^5\\ 1\leq K\leq 10^{18}\\ 1\leq A_i\leq 3×10^5}$

解説

${G=\gcd{(A_1,A_2,\cdots ,A_N)}}$ となるための最小操作回数が ${K}$ 以下であるかが分かればいい(そのような ${G}$ で最大のものが答え)．最大のものさえ見つけられればいいので「 ${G=\gcd{(A_1,A_2,\cdots ,A_N)}}$ 」を「 ${G|\gcd{(A_1,A_2,\cdots ,A_N)}}$ 」としてもいい．

${G|\gcd{(A_1,A_2,\cdots ,A_N)}\Leftrightarrow G|A_1\land G|A_2\land\cdots \land G|A_N}$ であるから，各 ${i}$ について ${G|A_i}$ となるための最小操作回数が分かればいい．これは ${\lceil A_i/G \rceil\times G-A_i}$ であるので ${\sum_{i=1}^{N}\lceil A_i/G \rceil\times G-A_i}$ が操作回数となる．これをすべての ${G}$ について求めればいいが， ${G}$ の取り得る範囲が大きいので間に合わない．

${A_{\max} < G}$ のとき， ${\lceil A_i/G \rceil=1}$ であるので ${\sum_{i=1}^{N}G-A_i\leq K \Leftrightarrow G\leq (K+\sum_{i=1}^{N}A_i)/N}$ より ${G=\lfloor (K+\sum_{i=1}^{N}A_i)/N\rfloor}$ が答え．ただし ${A_{\max}\leq\lfloor (K+\sum_{i=1}^{N}A_i)/N\rfloor}$ でないなら ${A_{\max}\leq G}$ の範囲に答えはない．

${A_{\max}\geq G}$ のとき， ${\lceil A_i/G \rceil}$ が同じ値である ${A_i}$ の数を計算すればいい． ${\lceil A_i/G \rceil = k}$ であるのは ${(k-1)G < A_i\leq kG}$ の範囲にあるものである．これは累積和を用いれば1つの範囲につき ${O(1)}$ で求められる．
${\sum_{G=1}^{A_{\max}}\lceil A_{\max}/G \rceil = O(A_{\max}\log{A_{\max}})}$ であるので全体で ${O(N+A_{\max}\log{A_{\max}})}$ となる．

提出プログラム

https://atcoder.jp/contests/arc126/submissions/26012713

感想

${A_{\max} < G}$ のとき簡単に分かることさえ気づけばすぐ．