(C++) - 백준(BOJ) 1629번 : 곱셈 답

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

1629번: 곱셈

 

풀이방법

a^b%c를 구하는 문제다.

a를 b번 곱하게 되면 O(b)의 시간이 거리게 되지만 

a ^ b/2 * a ^ b/2 로 곱하게 된다면 시간은 O(2 * logN)의 시간이 걸린다.

따라서 이 문제는 분할 정복 문제라고 볼 수 있다.

 

Code

#include <iostream>
using namespace std;
long long a, b, c;
long long cal(long long a, long long b, long long c)
{
    if (b == 0) { return 1; }
    else if (b == 1) { return a%c; }
    else if (b % 2 == 0) { long long tmp = cal(a, b / 2,c); return (tmp*tmp)%c; }//b가 짝수 일 때 a^b/2* a^b/2꼴로 나누어 푼다
    else //b%2==1 즉 b가 홀수 일 때 b를 짝수로 만들어주고 a를 곱해준다
        return (a * cal(a, b - 1,c))%c;
}
int main() {
    cin >> a >> b >> c;
    cout << cal(a, b, c)<<'\n';
    
}