Least Common Multiple
2つの正の整数 a と b が与えられます。最小公倍数、つまり a と b の両方で割り切れる最小の正の整数を返してください。
関数
- ainteger
- 最初の正の整数
- binteger
- 2番目の正の整数
- 戻り値integer
- a と b の両方の倍数である最小の正の整数
制約
1 ≤ a ≤ 1061 ≤ b ≤ 106- 答えは符号付き32ビット整数に収まります：
lcm(a, b) ≤ 231-1。積a × bは収まらない場合があります。
例
- 入力
- a = 4b = 6
- 出力
- 12
- 説明
6の倍数は6、12、18から始まり、4の倍数は4、8、12から始まります。両方のリストにある最初の数は12です。
- 入力
- a = 7b = 3
- 出力
- 21
- 説明
7と3は1以外に共通の因数を持たないため、最小公倍数は積の21です。
- 入力
- a = 15b = 45
- 出力
- 45
- 説明
15は45を割り切れるため、45はすでに両方の倍数であり、45より小さい倍数は存在しません。
発展問題
除算も剰余も一切使わず、引き算と半分にすることだけで最大公約数を求められますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
答えは大きい方の数の倍数です。その間のすべての数を試す必要がありますか、それとも大きい方の数の倍数だけでよいですか？
最大公約数と最小公倍数には次の関係があります：
gcd(a, b) × lcm(a, b) = a × b。ユークリッドの互除法を使うと、数十回ほどの手順で最大公約数を求められます。最大公約数を計算し、その後
a / gcd × bを返します。先に割り算をします。答えが収まる場合でも、積a × bは32ビット整数の範囲を超える可能性があります。
解説
最小公倍数と最大公約数には、次の関係があります：gcd(a, b) × lcm(a, b) = a × b。したがって、素早く答えを求めるにはa × b / gcd(a, b)を使います。積は10^12に達し、答えが収まる場合でも32ビット整数ではオーバーフローする可能性があるため、掛け算の前に最大公約数で割ってください。
大きい数から数え上げる
正しいが、最大のテストでは終わらない
考え方
答えは少なくとも大きい方の数です。mをmax(a, b)から始め、両方の数で割り切れるまで1ずつ加えます。候補を小さい順に試すため、最初に見つかった数が最小です。4と6の場合は、6から11まで試し、12で止まります。a × bは公倍数なので、ループは必ず終了します。
試行回数は答えの大きさとほぼ同じです。素数46337と46327の場合、答えは2146654199で、試行回数は20億回を超えます。
アルゴリズム
mをaとbのうち大きい方に設定します。m % aまたはm % bが0でない間、mに1を加えます。mを返します。
def lcm(a, b):
m = max(a, b)
while m % a != 0 or m % b != 0:
m += 1
return m大きい方の数の倍数を順に調べる
考え方
答えは大きい方の数であるbigの倍数なので、big、2 × big、3 × bigと順に調べ、小さい方の数で割り切れる最初の数で止めます。4と6の場合は、まず6、次に12を試します。
small × bigは常に公倍数なので、ループは最大でもmin(a, b)回、ここでは最大100万回実行されます。この制約なら十分高速ですが、入力値が大きくなるにつれて実行回数も増えます。数が10^18まである場合は、そうはいきません。
アルゴリズム
bigを大きい方の数、smallを小さい方の数とします。m = bigに設定します。m % smallが0でない間、mにbigを加えます。mを返します。
def lcm(a, b):
big, small = max(a, b), min(a, b)
m = big
while m % small != 0:
m += big
return m最大公約数で割ってから、掛ける
考え方
両方の数を素因数分解します。それぞれの素数について、gcd は2つのべきのうち小さい方を、lcm は大きい方を取るため、合わせると a と b のすべての因数をそれぞれちょうど1回ずつ使います。つまり、gcd × lcm = a × b です。4 = 2² と 6 = 2 × 3 の場合、gcd は 2、lcm は 2² × 3 = 12 です。
ユークリッドのアルゴリズムは、O(log(min(a, b))) ステップで gcd を求めます。その後、a / gcd × b の順に計算します。gcd は a を割り切るため、情報が失われることはなく、途中のどの値も答えを超えません。a × b / gcd の順で計算すると、a = b = 10^6 の場合に32ビット整数の範囲を超えます。このとき積は 10^12 ですが、答えはわずか 10^6 です。
アルゴリズム
aとbをxとyにコピーします。yが0でない間、(x, y)を(y, x % y)に置き換えます。これでxが gcd になります。aをxで割ります。- その結果に
bを掛けて返します。
def lcm(a, b):
x, y = a, b
while y != 0:
x, y = y, x % y
# x is gcd(a, b). Divide before multiplying.
return a // x * b
落とし穴と境界ケース
- 最初に
a × bを計算すること。Java、C、C++、C#、Rustでは、10^6に近い2つの数の積は32ビット整数でオーバーフローし、正しくない値や負の値になります（Rustのデバッグビルドではパニックが発生します）。lcmは収まる場合でも同様です。 - 浮動小数点数で割ること。結果が
2.146654199E9のようになったり、末尾の桁が失われたりすることがあります。すべて整数のまま扱いましょう。 aとbそのものにユークリッドのループを実行すること。その後、それらには最大公約数と0が入るため、コピーに対して処理しましょう。- 答えが
a × bだと思い込むこと。それが成り立つのは、2つの数に共通の因数がない場合だけです。lcm(4, 6)は24ではなく12です。
よくある質問3
2つの数の最小公倍数（LCM）の公式は何ですか？
lcm(a, b) = a × b / gcd(a, b)。中間値が答えを超えないよう、a / gcd(a, b) × bとして計算します。4と6の場合、gcdは2で、4 / 2 × 6 = 12となります。
最小公倍数（LCM）を計算する時間計算量はどのくらいですか？
最大公約数の公式を使うと、ユークリッドのアルゴリズムの計算量と同じく、時間計算量は O(log(min(a, b))) で、空間計算量は O(1) です。大きい方の数の倍数を順に調べる方法は O(min(a, b)) で、1ずつ数える方法は O(lcm(a, b)) です。
2つを超える数の最小公倍数はどのように求めますか？
リストを畳み込みます: lcm(a, b, c) = lcm(lcm(a, b), c)。[4, 6, 10]の場合、lcm(4, 6) = 12で、lcm(12, 10) = 60です。途中の値は急速に大きくなるため、リストが長い場合は64ビット整数を使いましょう。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def lcm(a, b):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
a = 4 b = 6
期待される出力
12