中級 0件解決済み 正答率0%

Modular Exponentiation

Compute base to the power exponent, modulo a number, with fast exponentiation.

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

  • Raise a number to a huge power in O(log exponent) steps
  • Keep every intermediate value reduced to avoid overflow
  • Handle exponent 0 and modulus 1

問題

翻訳を表示

Compute base^exponent mod modulus. The exponent can be as large as 10^18, so multiplying by base that many times is impossible; use exponentiation by squaring instead: look at the exponent's binary digits, square the base at every step, and multiply it into the result when the digit is 1. That takes about 60 steps for any exponent here.

Implement modular_exponentiation(base, exponent, modulus).

Reduce base modulo modulus first and after every multiplication. Since modulus ≤ 10^9, the product of two reduced values is below 10^18 and fits in a signed 64-bit integer.

Input

base: The base.

exponent: The power to raise the base to.

modulus: The number to take the remainder by.

Output

Return base^exponent mod modulus, a value from 0 to modulus − 1. Treat base^0 as 1 for every base, including 0, so the answer for exponent 0 is 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, and 1,594,323 = 50 × 31,886 + 23, so the answer is 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, and 1024 mod 1000 = 24.

解き方のヒント

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

ヒント 1

Look at the exponent one binary digit at a time, starting from the lowest.

ヒント 2

Square the base at every step and multiply it into the result when the current bit is 1.

ヒント 3

Start the result at 1 % modulus, so modulus 1 gives 0.

目安の計算量

O(log exponent) time, O(1) extra space

参考資料

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

ランキング

全体ランキング

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

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

他の人の解答から学ぶ

コミュニティの解答

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