アルゴリズム図鑑
ユークリッドの互除法
2つの整数の最大公約数を求める方法です。「大きいほうを小さいほうで割った余り」で置き換える操作を、余りが 0 になるまで繰り返します。
考え方
- a を b で割った余り r を求め、a ← b、b ← r と置き換える
- b が 0 になったときの a が最大公約数
- 引き算を繰り返すより、ずっと少ない回数で求まる
計算量
O(log n)
試験でのポイント
- mod は割り算の余りを求める演算子
- 代入の順番（a ← b を先、b ← r を後）を入れ替えると正しく動かない