AtCoder ABC148 C「Snack」の解き方｜GCDとLCMを使うPythonコード

AtCoder ABC148 C「Snack」で求めるのは、A人で分けてもB人で分けても余りが出ない、お菓子の最小個数です。答えはAとBの最小公倍数（LCM）。最大公約数をg = gcd(A, B)とすると、A // g * Bで求められます。この記事では4と6でGCD=2、LCM=12となる理由から、問題の入力を受け取るPythonコードと検算までたどります。

GCDとLCMの意味を4と6で確認する

GCD（最大公約数）は、2つの整数に共通する約数のうち最大のものです。LCM（最小公倍数）は、どちらの整数でも割り切れる正の数のうち最小のものです。GCDは共通の約数、LCMは共通の倍数を見ています。

4の正の約数は1、2、4で、6の正の約数は1、2、3、6です。共通する約数は1と2なので、最大のものは2、つまりGCDは2です。一方、4の倍数は4、8、12、…、6の倍数は6、12、…と並びます。最初に共通する正の数は12なので、LCMは12です。

ABC148 C「Snack」で求める値

AtCoder ABC148 C「Snack」の公式問題文では、A人でもB人でも均等に分けられるお菓子の最小個数を求めます。両方の人数で余りなく分ける条件は、個数がAとBの両方で割り切れることです。したがって、この問題はAとBの最小公倍数を出力する問題です。

入力は1行で、整数AとBが空白区切りで与えられます。
制約は1 ≤ A, B ≤ 10⁵かつA ≠ Bです。
出力するのはAとBの最小公倍数です。

GCDから最小公倍数を導く

公式解説の「C – Snack」節は、A、2A、3A、…とAの倍数を順に調べ、Bでも割り切れる最初の数を探す方法を説明しています。これは共通倍数を逐次探索する方法です。ここではその探索を繰り返すのではなく、最大公約数を使ってLCMを直接計算します。

問題の入力値をコードと同じ小文字のa、bで表し、g = gcd(a, b)とします。aとbはgで割り切れるため、a = g * x、b = g * yと書けます。xとyに2以上の共通約数があれば、その約数とgの積もaとbの共通約数になり、gより大きくなります。gが最大公約数であることに反するので、gcd(x, y) = 1です。

g * x * yは、a * yともb * xとも等しいため、aとbの両方で割り切れる共通倍数です。反対に、任意の共通倍数Mはaの倍数なのでM = g * x * kと書けます。Mがbの倍数でもあることから、yはx * kを割ります。xとyは互いに素なので、yはkを割り、Mはg * x * yの倍数です。つまりg * x * y自身が共通倍数で、ほかの共通倍数はその正の整数倍です。したがって、最小の共通倍数はg * x * yです。

a // g = xかつb = g * yなので、g * x * y = (a // g) * bとなります。4と6ならg = 2、x = 4 // 2 = 2、y = 6 // 2 = 3です。xとyは互いに素で、式は(4 // 2) * 6 = 12となり、最小公倍数を返します。

Pythonコードで入力から出力まで

Python標準ライブラリのmath.gcdは、整数引数の最大公約数を返します。これを使えば、標準入力からAとBを読み、GCDで割ってから掛ける処理をそのまま書けます。

import math
import sys

def solve():
    a, b = map(int, sys.stdin.readline().split())
    g = math.gcd(a, b)
    print(a // g * b)

if __name__ == "__main__":
    solve()

readline().split()で一行のA、Bを読み取り、map(int, ...)で整数にします。次にmath.gcd(a, b)でgを求め、a // g * bを出力します。gはaを割り切るので整数除算になり、出力は先ほど導いた最小公倍数です。

公式サンプル3件と独自例で検算する

次の上3行は公式問題文に掲載されたサンプルです。4と6の行は独自の追跡例で、公式サンプルではありません。掲載コードを各入力で実行した標準出力を並べています。

区分	入力（A B）	出力	計算の確認
公式サンプル1	`2 3`	`6`	GCDは1。`(2 // 1) * 3 = 6`
公式サンプル2	`123 456`	`18696`	GCDは3。`(123 // 3) * 456 = 18696`
公式サンプル3	`100000 99999`	`9999900000`	GCDは1。`100000 * 99999 = 9999900000`
独自例	`4 6`	`12`	GCDは2。`(4 // 2) * 6 = 12`

制約内の小さい入力1 2では2、上限近くの99999 99998では9999700002が出力されます。0、負の数、AとBが等しい入力は公式制約の範囲外であり、ここでは扱いません。

正しさと計算量

正しさは、g * x * yが共通倍数であり、任意の共通倍数がその倍数になることから分かります。コードはmath.gcdでgを得て、(a // g) * b = g * x * yを出力するため、求める最小の正の共通倍数を返します。

GCDを使う方法の時間計算量はO(log(min(A, B)))、補助領域はO(1)です。公式解説も、逐次探索とは別にLCMをO(log(min(A, B)))で求める方法に触れています。このコードはPython 3.11.9で標準入力から実行して確認しましたが、AtCoderには提出していないため、AC確認済みとはしていません。

この問題では、先にLCMを求めると見抜き、共通因数gを一度取り除いてから掛けるのがポイントです。4と6の例で式の各部分を確認しておけば、コードのa // g * bがなぜ最小値になるのかも説明できます。