【c++で楽しく実装!】ユークリッドの互除法

zuka

最大公約数をユークリッドの互除法で求めるよ。

本記事では,ユークリッドの互除法の簡単な解説と実装例をお伝えしていきます。使用言語はc++です。その他の競技プログラミング関連の記事は,以下の目次をご覧ください。

目次

本記事の概要

最大公約数を求める際に必要となる知識を復習していくものです。一般に,最大公約数を求める方法にはユークリッドの互除法が用いられます。高校数学でも習う知識ではありますが,しっかりとおさえておきましょう。なお,本記事では細かい証明や導出は省略します。

今回おさえるべき内容

 ユークリッドの互除法の定式化を確認する

 ユークリッドの互除法の計算量を確認する

 再帰を用いて実装できるようになる

定式化

$a$と$b$の最大公約数を$\mathrm{gcd}(a, b)$と表すことにします。ただし,$\mathrm{gcd}(x, 0)=x$とします。また,$a$を$b$で割った商を$q$,あまりを$r$とおきます。

\begin{align}
a &= qb + r
\end{align}

このとき,ユークリッドの互除法では以下のような関係を利用します。

\begin{align}
\mathrm{gcd}(a, b) &= \mathrm{gcd}(b, r) \label{gcd}
\end{align}

計算量

ユークリッドの互除法の計算量は$O\left(\log \{ \min(a, b) \} \right)$です。

ポイント

式($\ref{gcd}$)を利用して,再帰的にgcdを呼び出せば最大公約数を求められます。なぜなら,あまりの大きさは常に商よりも小さくなり,最終的にあまりは0になるからです。

\begin{alignat}{3}
\mathrm{gcd}(a, b) &= \mathrm{gcd}(b, r) &= \cdots &= \mathrm{gcd}(r’, 0)
\end{alignat}

上でお伝えしたように,$gcd(r’, 0)=r’$です。これは,$r’$と$0$の公約数が$r’$であることを意味しています。これにて,$a$と$b$の最大公約数が求められました。

\begin{alignat}{2}
\mathrm{gcd}(a, b) &= \mathrm{gcd}(r’, 0)
\end{alignat}

実装

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// ユークリッドの互除法の実装
ll gcd(ll a, ll b) {
  // あまりが0でなければ式(2)を再帰的に呼び出す
  // あまりが0になればそのときの商を返す
  return b != 0 ? gcd(b, a % b) : a;
}
よかったらシェアしてね!

コメント

コメントする

目次
閉じる