(C++) 백준 1629번 - 곱셈

문제 링크 : https://www.acmicpc.net/problem/1629

1629번: 곱셈

풀이

재귀를 활용하여 풀이하였다.

"n의 k승을 알면, n의 2k승과 n의 2k+1승을 알 수 있다."는 사실과 "(a x b) % k =  (a % k) x (b % k)"라는 사실을 활용하여 풀이를 진행하였다.

#include <iostream>

using namespace std;
using ll = long long;

int power(ll a, ll b, ll c){
    if(b == 0) return 1; // 모든 수의 0승은 1
    if(b == 1) return a % c; // 모든 수의 1승은 자기 자신
    if(b % 2 == 0) { // n의 2k승은 n의 k승 * n의 k승
        ll tmp = power(a, b/2, c) % c;
        return tmp * tmp % c;
    }else{ // n의 2k승은 n의 k승 * n의 k승 * n
        ll tmp = power(a, (b-1)/2, c) % c;
        // tmp가 매우 큰 수 일 수 있으므로 tmp * tmp 계산시에 모듈러 연산을 진행
        return ((tmp * tmp) % c) * a  % c; 
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);  

    ll a, b, c;
    cin >> a >> b >> c;
    cout << power(a, b, c);
}