ブログで書いてほしい内容受付中!! 詳しくはこちら

Python3 でN個の数の最小公倍数・最大公約数を求めたいとき【AtCoder】

サトゥー

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

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

注意

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

最大公約数はユークリッドの互除法を使って求められるよ Python では標準ライブラリ内の関数を使うと楽だよ 最小公倍数は最大公約数から計算できるよ

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

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

そもそも最大公約数とは

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

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

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

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

ユークリッドの互除法

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

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

$$gcd(a, b) = gcd(b, r)$$

サトゥー

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

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

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

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

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

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 の標準のライブラリには最大公約数を返す関数が入っています。これを利用して先程のコードと同じ内容を書いてみましょう。

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数の場合のアルゴリズムを繰り返し利用することで求めることができます。

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

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

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つの整数 \(a, b\) の最小公倍数(Least Common Multiple)は、 \(a, b\) の公倍数のうち最小のものを指し、これをしばしば \(lcm(a, b)\) と表記します。

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

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

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

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

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個の形式で与えられたとき、次のようにコードを書くことができます。

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 の過去問を使って練習してみます。

AtCoder ABC 070-C: Multiple Clocks

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

https://atcoder.jp/contests/abc070/tasks/abc070_c

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

解答案

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 もらいました。

AtCoder ABC 109-C: Skip

数直線上に \(N\) 個の都市があり、\(i\) 番目の都市は座標 \(x_i\) にあります。
あなたの目的は、これら全ての都市を \(1\) 度以上訪れることです。
あなたは、はじめに正整数 \(D\) を設定します。
その後、あなたは座標 \(X\) から出発し、以下の移動 \(1\)、移動 \(2\) を好きなだけ行います。
移動 \(1\) : 座標 \(y\) から座標 \(y+D\) に移動する
移動 \(2\) : 座標 \(y\) から座標 \(y−D\) に移動する
全ての都市を \(1\) 度以上訪れることのできる \(D\) の最大値を求めてください。
ここで、都市を訪れるとは、その都市のある座標に移動することです。

https://atcoder.jp/contests/abc109/tasks/abc109_c

少し数学的な考察が必要ですが、よく考えると、初期位置 \(X\) から各点までの距離を \(z = | X – x_{i} |\) としてしまえば、求めるべきは \(N\) 個の数 \(z_0, z_1, … , z_{N – 1}\) の \(GCD\) であることが分かります。

解答案

from fractions import gcd

N, X = map(int, input().split())
x = list(map(int, input().split()))
z = list(map(lambda i: abs(X - i), x))
ans = z[0]
for i in range(1, N):
	ans = gcd(ans, z[i])
print(ans)

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

コメントを残す

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

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