[백준 1629] 곱셈

🔗 알고리즘 문제

분할 정복을 이용한 거듭 제곱을 공부하게 된 문제이다. 해당 알고리즘도 꽤나 자주 사용되는 듯 싶어 나중에 한번 공부하여 정리해봐야겠다.

문제 분석

해당 문제는 a, b, c를 입력받아 a^b를 c로 나눈 나머지를 출력하는 간단한 문제이다.

발상 & 알고리즘 설계

int getnum(int n){
	int r = 1;
    
    for(int i = 0; i < n; i++){
    	r *= a;
    }
    
    return r;
}

위와 같은 단순한 for문을 통하여 a^n을 뽑을 순 있지만, 해당 문제에서는 최대값으로 2,147,483,647이 들어오기에 O(n)의 시간복잡도로는 문제를 해결할 수 없다.

따라서, 분할 정복을 이용하여 구현하여야 한다.

분할 정복을 간단히 설명하자면 다음과 같다.

a가 짝수일 때

a^n = a^n/2 * a^n/2

a가 홀수일 때

a^n = a^(n-1)/2 * a^(n-1)/2 * a

재귀를 이용하여 구현해주었다.

코드

#include<iostream>

using namespace std;

long long a;
long long b;
long long c;

long long getNum(long long n){
    if(n == 1){
        return a % c;
    }

    long long x = getNum(n / 2) % c;
    if(n % 2 == 0){
        return (x * x) % c;
    }
    else{
        return (((x * x) % c) * a) % c;
    }
}

int main(){
    cin >> a >> b >> c;
    cout << getNum(b);
}