c問題は解法が浮かんだが桁あふれを想定できていなかった。D問題は簡単だった。
https://atcoder.jp/contests/abc103
C問題
方針
全てのaについて最小公倍数を求めそこから-1をした数を各aで割ったあまりを求めていく問題。本質はこの考えで合っているが、最小公倍数を求める時桁あふれしてしまい、結果が変わるので、方針を変えなければならない。よく考えると明らかに、このあまりは各aの値-1であるので、各aについて-1をしたものを足していけば答えがでる。
D問題
方針
サンプルを絵に描いてみるとわかりやすいが、左端をソートしてみると、橋をきる回数を最小にするには明らかに多くの範囲を含む橋を切断した方が良い。また、いつひとまとめに切断するグループを切り替えるかを考えると左端をソートした後、右端の中で一番左端のものを更新していき、その右端よりも左端が大きいものがきた時、ひとまとめに切断するグループが切り替わることがわかる。よって、その切り替わった回数がすなわち切断回数なので、この回数が答えになる