백준 1629 - 곱셈

www.acmicpc.net/problem/1629

 

$A^{B} \mod C$ 를 빠르게 구해야 하는 문제이다.

 

단순하게 반복문을 통해 구한다고 하면 최대 2,147,483,647번 연산해야 하므로 이는 시간 내로 해결이 불가능하다.

 

따라서 해결을 위해서는 다른 방법이 필요하다. 이 문제 해결에 사용되는 알고리즘은 PS를 하는데 기본 소양이 되므로 그 방법을 잘 익히도록 한다.

 

예시로 $2^{1024}$를 구한다고 가정해보자.

 

$2^{1024}$는 $2^{1024} = 4^{512}$ 으로 나타낼 수 있다.

 

그러면 $4^{512}$도 $4^{512} = 8^{256}$ 으로 나타낼 수 있다.

 

이처럼 지수를 절반씩 쪼개가며 제곱하면 $O(\log n)$의 시간복잡도로 빠르게 계산할 수 있다.

 

지수를 절반으로 쪼개는 과정은 재귀를 통한 분할정복으로 간단하게 구현할 수 있다.

 

계산 과정 중 수가 int 범위를 넘어간다는 것과 제곱의 지수가 홀수인 경우와 1인 경우에 유의하여 구현하도록 한다.

 

전체 코드

#include <iostream>

using std::cin;
using std::cout;
using ull = unsigned long long;

ull power(ull x, ull y, ull m)
{
    if (!y) return 1;
    if (y == 1) return x % m;
    if (y & 1) return power(x, y - 1, m) * x % m;
    return power(x * x % m, y / 2, m) % m;
}

int main()
{
    ull a, b, mod;
    cin >> a >> b >> mod;
    cout << power(a, b, mod) << "\n";
}