問題
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
例
入力:
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 です。
入力:
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用に調整されています。上記の説明と制約に従ってください。