zuka最大公約数をユークリッドの互除法で求めるよ。
本記事では，ユークリッドの互除法の簡単な解説と実装例をお伝えしていきます。使用言語はc++です。その他の競技プログラミング関連の記事は，以下の目次をご覧ください。
目次
本記事の概要
最大公約数を求める際に必要となる知識を復習していくものです。一般に，最大公約数を求める方法にはユークリッドの互除法が用いられます。高校数学でも習う知識ではありますが，しっかりとおさえておきましょう。なお，本記事では細かい証明や導出は省略します。
今回おさえるべき内容
ユークリッドの互除法の定式化を確認する
ユークリッドの互除法の計算量を確認する
再帰を用いて実装できるようになる
定式化
$a$と$b$の最大公約数を$\mathrm{gcd}(a, b)$と表すことにします。ただし，$\mathrm{gcd}(x, 0)=x$とします。また，$a$を$b$で割った商を$q$，あまりを$r$とおきます。
\begin{align}
a &= qb + r
\end{align}
a &= qb + r
\end{align}
このとき，ユークリッドの互除法では以下のような関係を利用します。
\begin{align}
\mathrm{gcd}(a, b) &= \mathrm{gcd}(b, r) \label{gcd}
\end{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}
\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}
\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;
}
コメント