모든 챌린지
보통 0명 해결 정답률 0%

모듈러 거듭제곱

빠른 거듭제곱으로 base의 exponent제곱을 어떤 수로 나눈 나머지를 구합니다.

배우게 될 내용

  • O(log exponent) 단계로 아주 큰 지수의 거듭제곱을 계산할 수 있습니다
  • 중간값을 계속 나머지로 줄여 오버플로를 막을 수 있습니다
  • 지수가 0이거나 modulus가 1인 경우를 처리할 수 있습니다

문제

원문 보기 (영어)

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

예시

예시 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

지수를 가장 낮은 자리부터 한 비트씩 살펴보세요.

힌트 2

단계마다 밑을 제곱하고, 현재 비트가 1이면 결과에 곱하세요.

힌트 3

결과를 1 % modulus로 시작하면 modulus가 1일 때 0이 됩니다.

예상 복잡도

시간 O(log exponent), 추가 공간 O(1)

참고 자료

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

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