すべてのチャレンジ
中級 0件解決済み 正答率0%

べき乗の剰余(繰り返し二乗法)

繰り返し二乗法を使って、base の exponent 乗を modulus で割った余りを求めます。

このチャレンジで学べること

  • O(log exponent) ステップで、数を非常に大きな指数でべき乗する
  • 途中の値をすべて剰余で小さく保ち、オーバーフローを防ぐ
  • exponent が 0 の場合と modulus が 1 の場合に対応する

問題

原文(英語)を表示

base^exponent mod modulus を計算してください。exponent は最大 10^18 にもなるので、base をその回数だけ掛けるのは不可能です。代わりに繰り返し二乗法を使います。指数を 2 進数で見て、1 ステップごとに底を 2 乗し、そのビットが 1 なら結果に掛けます。この問題の範囲なら、どの指数でも約 60 ステップで済みます。

modular_exponentiation(base, exponent, modulus) を実装してください。

base は最初に modulus で割った余りにしておき、掛け算のたびにも余りをとります。modulus ≤ 10^9 なので、余りをとった値どうしの積は 10^18 未満となり、符号付き 64 ビット整数に収まります。

入力

base: 底。

exponent: 指数(底を何乗するか)。

modulus: 余りをとるときに割る数(法)。

出力

base^exponent mod modulus を、0 から modulus − 1 までの値で返してください。base^0 は、base が 0 の場合も含めて常に 1 とみなします。したがって、exponent が 0 のときの答えは 1 mod modulus です。

制約

0 ≤ base ≤ 10^18

0 ≤ exponent ≤ 10^18

1 ≤ modulus ≤ 10^9

例

例 1
入力:
base = 3
exponent = 13
modulus = 50

期待される出力:
expected = 23
入力:
long long base = 3;
long long exponent = 13;
long long modulus = 50;

期待される出力:
long long expected = 23;
入力:
long base = 3;
long exponent = 13;
long modulus = 50;

期待される出力:
long expected = 23;

解説

3^13 = 1,594,323 で、1,594,323 = 50 × 31,886 + 23 なので、答えは 23 です。

例 2
入力:
base = 2
exponent = 10
modulus = 1000

期待される出力:
expected = 24
入力:
long long base = 2;
long long exponent = 10;
long long modulus = 1000;

期待される出力:
long long expected = 24;
入力:
long base = 2;
long exponent = 10;
long modulus = 1000;

期待される出力:
long expected = 24;

解説

2^10 = 1024 で、1024 mod 1000 = 24 です。

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

指数を、いちばん下の桁から 1 ビットずつ見ていきましょう。

ヒント 2

1 ステップごとに底を 2 乗し、現在のビットが 1 なら結果に掛けます。

ヒント 3

結果を 1 % modulus から始めれば、modulus が 1 のときに 0 になります。

目安の計算量

時間 O(log exponent)、追加メモリ O(1)

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。