最初に \(a_i\) の約数を列挙し, 約数ごとに赤黒木に入れておく. このとき, \(a_i\) を固定したときの \(a_{i+1} \dots a_N\) の \(a_i\) との LCM の最小値は, 各約数ごとの赤黒木の最小値を拾ってきて \(a_i\) との LCM を計算したときの最小値である.

これは, \(x\) と \(y\) の LCM の計算は \(xy/g\) (\(g\) は \(x, y\) の最大公約数) であるので, このやり方で候補となる LCM はすべて列挙でき, またそうでない数も列挙してしまうがその数は \(a_i, a_j\) の LCM よりは必ず大きくなるので問題ない.