← 13주차 · 재귀와 분할 정복
보통분할 정복수학

거듭제곱 빠르게

정수 base, exp, mod가 주어져요. base를 exp번 곱한 값을 mod로 나눈 나머지, 즉 (base ^ exp) % mod를 반환해요.

base를 exp번 그냥 곱하면 O(exp)라 지수가 크면 느려요. 대신 base^exp = (base^(exp/2))²라는 관계를 쓰면 지수가 절반씩 줄어서 O(log exp)에 끝나요. 지수가 홀수면 base를 한 번 더 곱해 줘요.

나머지(mod)로 계산하는 이유는 곱이 너무 커지지 않게 하기 위해서예요. 곱할 때마다 mod를 취하면 값이 항상 작게 유지돼요.

예시

예시 1
입력
base = 2, exp = 10, mod = 1000
출력
24
설명
2^10 = 1024, 1024 % 1000 = 24 예요.
예시 2
입력
base = 3, exp = 5, mod = 100
출력
43
설명
3^5 = 243, 243 % 100 = 43 이에요.

제한 사항

  • 0 ≤ base ≤ 1,000,000,000
  • 0 ≤ exp ≤ 1,000,000,000
  • 1 ≤ mod ≤ 100,000
결과를 1로 시작하고 지수를 이진수처럼 훑어요. 지수가 홀수인 순간마다 현재 밑을 결과에 곱하고, 매 단계 밑을 제곱하면서 지수를 반으로 줄여요. 모든 곱셈 뒤에 % mod를 붙이면 값이 커지지 않아요.
javascript
function fastPower(base, exp, mod) {
  let result = 1 % mod;
  let b = base % mod;
  let e = exp;
  while (e > 0) {
    if (e % 2 === 1) result = (result * b) % mod;
    b = (b * b) % mod;
    e = Math.floor(e / 2);
  }
  return result;
}
이전 문제재귀 피보나치와 메모이제이션
다음 문제병합 정렬 직접 구현
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.