0Pricing
Competitive Programming Academy · レッスン

GCD、LCM、ユークリッドの互除法

約数を高速かつ正確に計算します

「GCD、LCM、ユークリッドの互除法」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。

約数が重要な理由

コンテスト問題の多くは、2 つの数に共通する因数が鍵になります。ここで最も役立つ道具は、最大公約数である GCD です。🔢

GCD の意味

2 つの整数のGCDとは、どちらも余りなく割り切れる最大の数です。12 と 18 の GCD は 6 です。6 は両方を割り切れるからです。

遅い方法

小さい方の値から数を 1 つずつ下げ、両方を割り切れる数が見つかるまで調べることもできます。動作しますが、大きな入力には遅すぎます。

ユークリッドの着眼点

ユークリッドの互除法が高速な方法です。重要な考え方は、a と b の GCD が、b と a を b で割った余りの GCD に等しいということです。

漸化式

余りが 0 になるまで、入れ替えと mod の手順を繰り返します。最後に残る 0 でない値が答え、つまり GCD そのものです。

gcd(a, b) = gcd(b, a % b)
gcd(a, 0) = a

自分でコードを書く

短いループで、b が 0 になるまで組を置き換え続けます。必要なステップ数はおよそ log で、非常に大きな数でも驚くほど高速に動作します。

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

標準ライブラリを使う

通常は自分で実装する必要はありません。Python には math.gcd が用意されており、正確で高速なうえ、引数が 0 の場合も処理してくれます。

from math import gcd
print(gcd(12, 18))

GCD から LCM へ

LCM（最小公倍数）とは、両方の値で割り切れる最小の数です。これは、先ほど計算した GCD と直接つながっています。

LCM の公式

2 つの数を掛けてから、GCD で割ります。非常に大きな積でのオーバーフローを避けるため、必ず先に割ってください。

def lcm(a, b):
    return a // gcd(a, b) * b

リスト全体の GCD

複数の数に対して GCD を順に適用するには、2 つずつ連鎖させます。Python の reduce は、リストに対して math.gcd を左から右へ適用します。

from functools import reduce
from math import gcd
g = reduce(gcd, nums)

0 の場合を扱う

定義上、gcd(a, 0) は a で、gcd(0, 0) は 0 です。この端のケースを知っておくと、空の入力でもループが誤動作しません。

確認

ユークリッドの互除法の中心となる手順を確認します。

まとめ

これで、ユークリッドの互除法を使って GCD を log ステップで計算し、そこから LCM を求め、リスト全体に対して両方を順に適用できるようになりました。✅

よくある質問

「GCD、LCM、ユークリッドの互除法」レッスンは無料ですか？

はい。「GCD、LCM、ユークリッドの互除法」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。

「GCD、LCM、ユークリッドの互除法」で何を学びますか？

約数を高速かつ正確に計算します ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。

「GCD、LCM、ユークリッドの互除法」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. GCD、LCM、ユークリッドの互除法
  2. sqrt(n) までの素数判定
  3. エラトステネスのふるい
  4. 素因数分解と約数
← Competitive Programming Academyに戻る