ヒント → https://atcoder.jp/contests/arc166/editorial/7181

[1] 解法 (1)

各項に対する操作は次のどれかとしてよいです．

• 何もしない．
• \(a\) の倍数になるまでインクリメントする．
• \(b\) の倍数になるまでインクリメントする．
• \(c\) の倍数になるまでインクリメントする．
• \(\mathrm{lcm}(a,b)\) の倍数になるまでインクリメントする．
• \(\mathrm{lcm}(a,c)\) の倍数になるまでインクリメントする．
• \(\mathrm{lcm}(b,c)\) の倍数になるまでインクリメントする．
• \(\mathrm{lcm}(a,b,c)\) の倍数になるまでインクリメントする．

先頭の項から順に \(8\) 種のうちどの操作をするか決めていきながら，各時点で \(a, b, c\) の倍数がそれぞれ存在するという条件を達成しているかという \(8\) 状態に対する最小コストを計算するという dp により，\(O(N)\) 時間で解くことができます．

[2] 解法 (2)

目的を達成するためには，次のような方法があります．

• 異なる項を \(a\) の倍数，\(b\) の倍数，\(c\) の倍数にする．
• 異なる項を \(a\) の倍数，\(\mathrm{lcm}(b,c)\) の倍数にする．
• 異なる項を \(b\) の倍数，\(\mathrm{lcm}(a,c)\) の倍数にする．
• 異なる項を \(c\) の倍数，\(\mathrm{lcm}(a,b)\) の倍数にする．
• ある項を \(\mathrm{lcm}(a,b,c)\) の倍数にする．

これらそれぞれに対して解きましょう．どれも同じなので最初の場合を解説します．

単に全探索することを考えると，どの項を \(a,b,c\) の倍数にするかを決める \(\Theta(N^3)\) 通りの探索が必要になりそうです．

探索範囲を減らすために，最適解に仮定できる性質を考察すると，例えば次のことが分かります：

• \(a\) の倍数にする項が，そのためのコストが小さい方から \(3\) つ以内のどれかであるような最適解が存在する．

実際，\(a\) の倍数にする項をとりかえる操作を考えることで簡単に証明できます．このように操作対象とする項を \(O(N)\) 時間かけて \(O(1)\) 個に絞り込んだあとで全探索を行うことで，\(O(N)\) 時間で解くことができます．