\(S = \sum A_i\) とすると, 操作後も \(S\) は変わらない. よって, \(\{ A_i \}\) の公約数は \(S\) の約数である.

\(\{ A_i \}\) の公約数を \(d\) として操作後にすべての \(A_i\) を \(d\) の倍数にするための必要回数を考える.

まず, \(d\) の倍数にする回数を数えるので, \(A_i\) を \(d\) で割ったあまりだけ考えればいい. これを \(B_i\) とする.

次に \(\sum B_i = kd\) として, \(k\) 個を \(B_i-d\) に置き換える. こうすることで, \(\sum B_i = 0\) となる. このとき, \(B_i \gt 0\) の合計が操作回数となる. 操作回数をできるだけ少なくするには, \(B_i\) の大きい方から \(k\) 個を \(B_i - d\) に置き換えるのが最適である.

このようにして求めた \(d\) が \(K\) 以下であれば操作後の公約数を \(d\) にすることができる.