모든 챌린지
보통 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

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위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.