Least Common Multiple
2つの正の整数 a と b が与えられます。最小公倍数、つまり a と b の両方で余りなく割り切れる最小の正の整数を返してください。
たとえば、6 の倍数は 6、12、18、24 などで、8 の倍数は 8、16、24 などです。両方のリストに含まれる最初の数は 24 です。
関数
- 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より小さい倍数は存在しません。
提出時に隠しテスト+15件
発展問題
割り算も余りの計算も一切使わず、引き算と半分にする操作だけで最大公約数を求められますか？
ヒント
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) から始め、a と b の両方で割り切れるまで1ずつ増やします。候補を小さい順に試すので、最初に条件を満たすものが最小です。
4 と 6 の場合は、6、7、8、9、10、11を試しますが、どれも条件を満たさず、12 で終了します。a × b は公倍数なので、ループは必ず終了します。
試行回数は答えの大きさとほぼ同じです。2つの素数である 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 を試します（4では割り切れません）。次に 12 を試すと、割り切れます。答えはある k に対する k × big で、k は小さい方の数以下です。なぜなら、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最大公約数で割ってから、掛ける
考え方
両方の数を素因数に分解します。最大公約数では、それぞれの素因数の2つの指数のうち小さい方を取り、最小公倍数では大きい方を取ります。これらを合わせると、a と b のすべての因数をそれぞれちょうど1回ずつ使うことになります。したがって、gcd(a, b) × lcm(a, b) = a × b となり、lcm(a, b) = a × b / gcd(a, b) です。4 = 2² と 6 = 2 × 3 の場合、最大公約数は 2、最小公倍数は 2² × 3 = 12 です。
ユークリッドの互除法で最大公約数を求めます。y が 0 になるまで、(x, y) を (y, x % y) に置き換えます。これにかかるステップ数は O(log(min(a, b))) です。
次に、a / gcd × b の順に計算します。最大公約数は 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が最大公約数になります。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
落とし穴と境界ケース
式は1行ですが、バグは算術演算の順序にあります。
- まず
a × bを計算すること。Java、C、C++、C#、Rustでは、10^6に近い2つの数の積は32ビット整数の範囲を超えるため、答えが誤った値や負の値になります（Rustのデバッグビルドでは代わりにパニックが発生します）。真の最小公倍数が範囲内に収まる場合でも同様です。 a × bを浮動小数点数で最大公約数で割ること。結果が2.146654199E9になったり、末尾の桁が失われたりすることがあります。すべて整数のまま扱いましょう。aとb自体を使ってユークリッドのループを実行し、その後それらを公式に使うこと。ループの後には、それらには最大公約数と0が入っているので、コピーを使って計算しましょう。- 答えが
a × bだと思い込むこと。これは2つの数が互いに素の場合に限られます。lcm(4, 6)は24ではなく12です。
よくある質問4
2つの数の最小公倍数を求める公式は何ですか？
lcm(a, b) = a × b / gcd(a, b) は、途中の値が答えを超えないように a / gcd(a, b) × b として計算します。4 と 6 の gcd は 2 で、4 / 2 × 6 = 12 です。
なぜ gcd(a, b) × lcm(a, b) は a × b に等しいのでしょうか？
各素数について、gcd は a と b におけるその素数の累乗の小さい方を使い、lcm は大きい方を使います。小さい方と大きい方を足すと両方の累乗の和になり、これは a × b におけるその素数の累乗とちょうど一致します。すべての素数について成り立つため、2つの積は等しくなります。
LCM を計算する時間計算量はどのくらいですか？
gcdの公式を使う場合、計算量はユークリッドのアルゴリズムのコストである O(log(min(a, b))) に、除算1回と乗算1回を加えたものです。追加で必要な領域は 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問解くとパターンが身につきます。
Python
def lcm(a, b):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
a = 4 b = 6
期待値
12