Python 3 でN個の数の最小公倍数・最大公約数を求めたいとき

サトゥー

AtCoderの勉強をはじめて、毎日コツコツA問題からこなしています。

今日は自分の引き出しの整理のために、 Python3 で最小公倍数・最大公約数を求める方法について整理します。

注意

AtCoder での仕様を想定しているため、 Python 3.4.3 を想定しています。

2数の最大公約数の求め方

まずは2数の最大公約数を求めます。これをN個の数に応用することを見据えて、考えていきましょう。

そもそも最大公約数とは

まずはここから簡単に復習します。 2つの整数 \displaystyle a, b の最大公約数(Greatest Common Divisor)とは、 \displaystyle a, b の公約数(共通の約数)のうち最大の数をいいます。(細かいですが \displaystyle a, b は0でない整数です)

最大公約数の英語表記に当たる Greatest Common Divisor の頭文字をとって、しばしば \displaystyle gcd(a, b) と表記したりします。

たとえば、 \displaystyle gcd(12, 18) = 6, gcd(9, 20) = 1 などと言えますね。

高校の数学では整数論の重要な要素の一つとして出てきますね。しばしば整数絡みの問題解決で利用できる重要な数にあたるので、ここで求め方を知っておきましょうというワケです。

ユークリッドの互除法

最大公約数を求める際には ユークリッドの互除法 という有名な手法が利用されます。原理は単純ですし、重要な概念なので是非覚えてってください。

自然数 \displaystyle a, b (a \geq b) に対し \displaystyle a\displaystyle b で割ったあまりを \displaystyle r とすると、次の式が成り立つ。

\displaystyle gcd(a, b) = gcd(b, r)

サトゥー

ちなみに、ユークリッドの互除法は世界最古のアルゴリズムと呼ばれているそうですよ。

 

ユークリッドの互除法の原理的なものに当たるのですが、以下の事実は覚えておくと整数分野で役に立つかもです。(完全に数学の話になってしまいました)

整数 \displaystyle a, b について、 \displaystyle a, b の公約数の集合は、 \displaystyle a - b, b の公約数の集合と一致する

これが成り立つので、当然 \displaystyle gcd(a, b) = gcd(a - b, b) が成立します。(証明はカンタンです)よって、これを繰り返し利用すればユークリッドの互除法が説明できます。なぜかって、 \displaystyle a から \displaystyle b を引けるだけ引いたら残りが \displaystyle r になるからですね。

これを用いると、例えば次のように大きな数同士の gcd でも比較的簡単に求めることができます。

gcd(58585, 18184)
= gcd(4033, 18184) (58585 = 18184 * 3 + 4033)
= gcd(4033, 2052) (18184 = 4033 * 4 + 2052)
= gcd(1981, 2052) (4033 = 2052 * 1 + 1981)
= gcd(1981, 71) (2052 = 1981 + 71)
= gcd(64, 71) (1981 = 71 * 27 + 64)
= gcd(64, 7) (71 = 64 * 1 + 7)
= gcd(1, 7) (64 = 7 * 9 + 1)
= 1

 

2数の最大公約数を求める

さて、事前知識もだいたいさらったので、ユークリッドの互除法をつかって gcd(a, b) を求めてみましょう。

  • 2つの正の整数 a b が入力される (a > bになるように自分で調整)
  • ユークリッドの互除法を利用して gcd(a, b) が計算される
  • gcd(a, b) が出力される

この流れをコードに起こしてみると、次のようになります。

Python3
a, b = map(int, input().split())
if a < b:
    a, b = b, a
while a % b != 0:
    a, b = b, a % b
print(b)

最大公約数を求める関数

丁寧に gcd(a, b) の処理についてここまで見てきましたが、実は Python の標準のライブラリには最大公約数を返す関数が入っています。これを利用して先程のコードと同じ内容を書いてみましょう。

Python3
import fractions
a, b = map(int, input().split())
print(fractions.gcd(a, b))

簡単でしたね。

参考 fractions.gcd() --- 有理数Python 3.7.3 ドキュメント
注意

バージョン 3.5 以降では fractions モジュールではなく math モジュールに gcd() 関数があるので注意が必要です。

N個の数の最大公約数の求め方

一般の場合、N個の数の最大公約数は、2数の場合のアルゴリズムを繰り返し利用することで求めることができます。

たとえば、 \displaystyle 16, 100, 4000 の最大公約数は、 \displaystyle gcd(16, 100) = 4 より、 \displaystyle gcd(4, 4000) = 4 と求めることができますね。

入力が a[0] a[1] a[2] ... a[N-1] のN個の形式で与えられたとき、次のようにコードを書くことができます。

Python3
import fractions
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, N):
    ans = fractions.gcd(ans, a[i])
print(ans)

やってることは単純で、

  •  gcd 関数をもつ fractions モジュールを import
  •  a という配列に入力される N 個の値を入れる
  • はじめ ans = a[0] として、以降は ansgcd(ans, a[i]) を代入していく (i = 1, 2, …, N – 1)
  • こうして最終的に求まった ans が求める最大公約数

といった感じ。

 

2数の最小公倍数の求め方

次に最小公倍数を見ていきましょう。2つの整数 \displaystyle a, b の最小公倍数(Least Common Multiple)は、 \displaystyle a, b の公倍数のうち最小のものを指し、これをしばしば \displaystyle lcm(a, b) と表記します。

整数論で出てくるような具体値の最小公倍数を求めるシチュエーションでは、素因数分解でもして指数部分を比較してやれば簡単に求まりますが、 Python では次のような関係式を上手く利用することで簡単に求めることができます。

\displaystyle gcd(a, b) \cdot lcm(a, b) = a \cdot b

これより、 \displaystyle lcm(a, b) = \frac{a \cdot b}{gcd(a, b)} が成り立ちますから、最大公約数 \displaystyle gcd(a, b) を求めてしまえば瞬時に求まることが分かりますね。

これを元に、先程の \displaystyle lcm(a, b) を求めるプロセスと合わせて 2数の最小公倍数を求めるプログラムを考えてみます。

Python3
import fractions
a, b = map(int, input().split())
print(a * b // fractions.gcd(a, b))

a * b // fractions.gcd(a, b) としたのは、 / だと値が float 型になってしまうためです。念のため。

N個の数の最小公倍数の求め方

あとはこれを一般のN個の数の最小公倍数の求め方にまで落とし込めれば、 Python で最大公約数・最小公倍数の話が出てきたときに一瞬で処理ができるようになりますね。

入力が a[0] a[1] a[2] ... a[N-1] のN個の形式で与えられたとき、次のようにコードを書くことができます。

Python3
import fractions
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, N):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
print(ans)

練習

最後に、実際に AtCoder の過去問を使って練習してみます。

ABC 070-C: Multiple Clocks

\displaystyle N 台の時計があり、 \displaystyle i (1 \geq i \geq N) 番目の時計の針はちょうど \displaystyle T_{i} 秒で時計板を 1 周します。
最初、すべての時計の針はまっすぐ上を向いており、止まっています。
イルカは、すべての時計の針を同時に動かし始めました。再び、すべての時計の針がまっすぐ上に向くのは何秒後でしょうか?

\displaystyle T_1 ~ \displaystyle T_{N} の最小公倍数を求めよということです。さっきやったばかりですね。

解答案

Python3
import fractions
N = int(input())
T = list(int(input()) for _ in range(N))
ans = T[0]
for i in range(1, N):
    ans = ans * T[i] // fractions.gcd(ans, T[i])
print(ans)

これで AC もらいました。

 

振り返ってみれば、最小公倍数・最大公約数を求める方法は単純でしたが、こういったよく利用する処理を頭の中に沢山ストックしておけると良さげですね。

コメントを残す

メールアドレスが公開されることはありません。

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)