0Pricing
Coding Interview Prep · レッスン

高速なモジュラーべき乗

pow(a, b, m) で累乗を計算します

「高速なモジュラーべき乗」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

べき乗の問題

大きな指数で数をべき乗し、その結果をすべて modulus の下で求めなければならないことがよくあります。因子を1つずつ掛ける方法では、ステップ数が多すぎます。⚡

素朴な方法では遅すぎる

b 回掛けるループは O(b) ステップかかります。指数が10億近くあると、処理が終わる前に制限時間を大幅に超えてしまいます。

for _ in range(b): r = r * a % MOD

二乗して高速に進む

コツは二乗です。a の8乗は、((a の二乗)の二乗)の二乗と表せます。二乗するたびに指数が2倍になるため、少ないステップで大きなべき乗に到達できます。

指数を2進数で読む

すべての指数は、2のべき乗の和、つまり2進数で表せます。そのため、ビットが立っている位置の基数のべき乗だけを掛け、残りは飛ばせます。

# 13 = 1101 -> a^8 * a^4 * a^1

最下位ビットを確認する

b & 1 を調べると、最下位ビットを確認できます。1 であれば、次に進む前に現在の基数を計算中の結果へ組み込みます。

if b & 1: result = result * base % MOD

毎回シフトして二乗する

各ビットを処理したら、基数を二乗し、指数を右に1ビットシフトします。現実的な入力であれば、ループは約30〜60回しか実行されません。

base = base * base % MOD
b >>= 1

全体を組み立てる

result を 1 で始め、指数が正である間ループします。この高速べき乗法は、二進法や繰り返し二乗法とも呼ばれます。

result = 1
while b > 0:
    if b & 1: result = result*base%MOD
    base = base*base%MOD
    b >>= 1

対数時間で実行できる

各ラウンドで指数が半分になるため、計算量は O(log b) です。これにより、10億回の乗算が約30回になり、どのような制限時間でも十分間に合います。

Python なら pow が使える

ループを自分で書く必要はほとんどありません。Python 組み込みの pow(a, b, m) が、C 並みの速度で高速な mod べき乗を実行してくれます。

print(pow(2, 100, MOD))

すぐに役立つ理由

高速べき乗は、次に学ぶフェルマーの法逆元を求める処理の基盤です。今のうちに身につければ、mod の下での割り算が簡単になります。

まず基数を確認する

ループの前に base % MOD で基数を小さくします。基数が modulus より大きいままだと、二乗するたびに値が不必要に大きくなります。

base = a % MOD

確認問題

高速な mod べき乗の計算量はどれくらいでしょうか。

まとめ

これで、二乗とビットの読み取りによって、巨大な指数のべき乗を O(log b) で計算できるようになりました。Python では pow(a, b, m) を呼び出すだけです。🚀

よくある質問

「高速なモジュラーべき乗」レッスンは無料ですか？

はい。「高速なモジュラーべき乗」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「高速なモジュラーべき乗」で何を学びますか？

pow(a, b, m) で累乗を計算します ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

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

「高速なモジュラーべき乗」レッスンにはどのくらい時間がかかりますか？

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

このCoding Interview Prepレッスンでコードを書いて実行できますか？

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

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

  1. 素数を法とする計算
  2. 高速なモジュラーべき乗
  3. フェルマーの小定理による逆元
  4. 前計算した階乗による nCr
← Coding Interview Prepに戻る