Go言語で最大公約数を求める（ユークリッドの互除法）

まずは、コードです。Go言語で最大公約数を求める関数は以下になります。「こんなにシンプルなの？」と思うかもしれませんが、こんなにシンプルです。簡単な説明も書きましたので興味があったら読んでください。

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

拡張ユークリッドの互除法については以下の記事を参考にしてください

あわせて読みたい

拡張ユークリッドの互除法の使い方・応用例を解説【Python/Go】

その他のAtCoderに役立つ記事の一覧は以下にあります。

あわせて読みたい

AtCoderで役立つ記事一覧（Python, Go言語）

はじめに

AtCoderをやっていると結構使う最大公約数を求めると言う処理ですが、簡単に書くことができます。ここでは、最大公約数を求める方法を簡単に説明し、Go言語でコードを書いてみたいと思います。

ユークリッドの互除法

ユークリッドの互除法は、以下のような手順を繰り返すものになります。

自分としては、以下のように考えた方がわかりやすかったのでその流れで説明します。

ユークリッド互除法は、長方形を正方形で分割していく例で説明されていますが、ここでは、正方形を長方形に敷き詰めた図にしました。

本来は、このグリッドがない状態で敷き詰められる最大の正方形のサイズ（＝最大公約数）を求める問題なのですが、あらかじめ補助線として正方形を配置した図で考えることでわかりやすく（？）なるかと思います。

縦・横同じサイズを切り出した場合、縦も横も同じ長さで分割できるるはずです。なので、まず赤色の部分を除外します。

残った部分から、さらに正方形（緑色の部分）を除外します。

これを残りの部分の縦と横が等しくなるまで繰り返します。

図では水色の部分を除外した残った部分の縦と横が等しくなっている（＝敷き詰めた正方形のサイズになった）ので、これが求める値となります。

上の説明は、一部正しくないのですが、自分はイメージしやすかったので上記の説明を使っています（具体的には、横が極端に長い場合などは、正方形が取れなくなるまで複数個取るような操作を行う必要があります）。

ちなみに、縦・横が同じサイズかどうかは、$a \leqq b$の場合であればb%aが0かどうかで判定できます。

Go言語による実装

ユークリッドの互除法は再帰を使って実装すると簡単です。

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

たった、これだけです。

プログラムの流れは以下のようになります。処理量ですが、毎回bで割ったあまりをとる（つまり、どんどん割っていく）ので、ループ数もそれほどないことがわかります。

計算量はO(log(min(a, b))です

• bが0になった場合は余りが０になったと言うことなので、aを返す
• それ以外の場合は、gcd(b, a%b)として繰り返す（共通の正方形を取り除く処理に相当します）

ライブラリ化するのも良いですが、これくらいはサッと書けるようになると良いかと思います。

ちなみに、最小公倍数は以下の数式になります。割り算を先にするのはオーバーフローを防ぐためです。

func lcm(a, b int) int {
  return a / gdc(a, b) * b
}

終わりに

最大公約数を求める方法を解説し、Go言語で関数を作成してみました。結構簡単なので、覚えておくと良いかと思います。