リストと集合で大きく違う！"if A in B"の処理速度の罠｜Python
Aru
Aru's テクログ（Aruaru0）
Go言語で最大公約数を求める（ユークリッドの互除法）
Aru
この記事では、Go言語で最大公約数（GCD）を求める方法を紹介します。コードは下記の通りです。非常にシンプルなこのコードは「ユークリッドの互除法」と呼ばれるもので、これだけで最大公約数を求めることができます。アルゴリズムの基本的な考え方などについても記事にまとめましたので興味があれば読んでみてください。
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}拡張ユークリッドの互除法については以下の記事を参考にしてください
あわせて読みたい
拡張ユークリッドの互除法の使い方・応用例を解説【Python/Go】
その他のAtCoderに役立つ記事の一覧は以下にあります。
あわせて読みたい
AtCoderで役立つ記事一覧（Python, Go言語）
Contents
はじめに
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言語で関数を作成してみました。結構簡単なので、覚えておくと良いかと思います。
ABOUT ME
専門分野は並列処理・画像処理・機械学習・ディープラーニング。プログラミング言語はC, C++, Go, Pythonを中心として色々利用。現在は、Kaggle, 競プロなどをしながら悠々自適に活動中
