[백준] 1629 - 곱셈 (C++)

문제

https://www.acmicpc.net/problem/1629

풀이

단순히 반복문을 돌려 거듭제곱을 한다면, 반복문이 최대 2,147,483,647번을 돌게 되어 시간 초과를 받게 됩니다.
다른 방식을 생각해야 하는데, 이때 사용되는 것이 분할 정복을 이용한 거듭제곱입니다.

거듭제곱을 수학적으로 분할해 본다면, 아래와 같은 식을 구성할 수 있습니다.

$a^b = a^{ \frac{b}{2}} \times a^ \frac{b}{2}$ - 지수가 짝수일 때
$a^b = a^{ \frac{b}{2}} \times a^{ \frac{b}{2} + 1}$ - 지수가 홀수일 때

위 식을 그대로 코드로 구현하고, 중복되는 연산을 줄이기 위해 temp 변수를 하나 더 선언하여 계산하면 됩니다.
나머지 연산도 연산 결과마다 꾸준히 해줍니다.

#include <iostream>
using namespace std;

long long pow(long long A, long long B, long long C) {
  // 0과 1 예외 처리 (0제곱: 1, 1제곱: 그대로 나머지 결과 반환)
  if (B == 0) return 1;
  if (B == 1) return A % C;

  long long temp = pow(A, B / 2, C);
  if (B % 2 == 0) return (temp * temp) % C; // 지수가 짝수일 때
  else return (((temp * temp) % C) * A) % C; // 지수가 홀수일 때
}

int main() {
  long long A, B, C;
  cin >> A >> B >> C;

  cout << pow(A, B, C);

  return 0;
}

여담으로, 파이썬 pow() 함수에는 나머지를 구하는 기능이 내장되어 있어, 한줄 코딩을 할 수 있습니다.

print(pow(*map(int,input().split())))