atcoder.jp これは300点問題なんだけど、なんか話題になっていたのでまずユークリッドの互除法でgcdを求めるコードを書いておく。これの計算量はラメの定理により十進法での桁数くらいらしいですね（知らなかった）、すごい。まず、書き換える時は10^9以下な…