ABC 070 C問題 Multiple Clocks

競技プログラミングの問題解いた振り返りを残していくといいとどこかで聞いたので，恥さらしを始めてみます．

かかった時間：25min 1発AC

考察の過程

T_i　（1≦i≦N）　の最小公倍数が答えになる．

愚直解としては，答えは10¹⁸以下であることがわかっているので1以上10¹⁸以下の範囲の整数をすべて試して，それらがすべてのT_i　（1≦i≦N）で割り切れるか判定すればいいけど，O(10¹⁸ × 100)で間に合わない．

では，最小公倍数を求められるもっと計算量の小さいアルゴリズムはないか？約数問題で軽いアルゴリズムといえばユークリッドの互除法（整数aとbの最大公約数の計算量はO(log max(a,b)) ）→最大公約数を使って最小公倍数を求めていけないか？

→lcm(i)をT_1〜T_iの最小公倍数とする．lcm(i+1)=lcm(i)×T_i / (lcm(i)とT_iの最大公約数)　なのでiを1〜Nまで動かしていけば，計算量がO(N log(max(T_i)))

という感じで考えました．

コード

Submission #2791105 - AtCoder Beginner Contest 070

反省

• 計算量から解法を考えられるようになったのは成長した．
• ユークリッドの互除法を思い出すことができた．
• はじめ，lcm(i+1)=lcm(i)×T_i / (lcm(i)とT_iの最大公約数)の計算で桁あふれすることを考慮してなくておかしな結果になってなんでだろ〜？となり時間がかかってしまった…どうも，大きな数同士の計算の桁あふれに鈍感な傾向にあるので，今後の気をつけるポイント．
• コードを見返すとlcm(i)とT_i のmax，minを取るという無駄な処理をしている…
• とはいえ少し前までは解法すら思い浮かばなかったと思うのでこれでも進歩しているのです．