문제
base^exponent mod modulus를 계산하세요. 지수는 최대 10^18이므로 base를 그만큼 곱하는 것은 불가능합니다. 대신 분할 정복을 이용한 거듭제곱(exponentiation by squaring)을 쓰세요. 지수를 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 사이의 값을 반환합니다. 0을 포함한 모든 base에 대해 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
지수를 가장 낮은 자리부터 한 비트씩 살펴보세요.
힌트 2
단계마다 밑을 제곱하고, 현재 비트가 1이면 결과에 곱하세요.
힌트 3
결과를 1 % modulus로 시작하면 modulus가 1일 때 0이 됩니다.
예상 복잡도
시간 O(log exponent), 추가 공간 O(1)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.