No.368

$a_i$ をすべて素因数分解する.

ある素因数 $p$ が $a_i$ に $q_i$ 個含まれているとする.

このとき, 要素数が $K$ の $\{q_i\}$ の部分列を考えると, その部分列の和の最大値が LCM に含まれる $p$ の乗数となる.

和の最大値は $q_i$ が大きい順に $K$ 個取ればいい.