かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

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}のとき簡単に分かることさえ気づけばすぐ.