백준 1629번, 곱셈

백준 1629번 c++ 문제풀이

문제:

백준 1629

풀이:

1. 분할정복으로 쪼개서 접근한다.
2. 지수가 1이 될떄까지 재귀함수를 이용해서 쪼개준다.
3. 모듈러 법칙이란 (a*b) % c = {(a % c) * (b % c)} % c 이다.
4. 위의 법칙과과 지수 법칙을 적용해 쪼개준다.
5. a^b % c를 구하려면 먼저 b가 짝수인지 홀수인지 구분해줘야한다.
6. b가 짝수이면 a^b%c = (a^b/2 % c * a^b/2 % c) % c
7. b가 홀수이면 a^b%c = (a^b/2 % c * a^b/2 % c * a % c) % c
8. b = 1이면 a%c, 0이면 1이다.

코드:

#include <iostream>
#include <algorithm>

using namespace std;

long long divide(long long a, long long b, long long c){
    if(b == 1){
        return a % c;
    }
    if(b == 0){
        return 1;
    }

    long long t = divide(a, b/2, c) % c;

    if(b%2 == 0){//지수가 짝수라면
        return t * t % c;
    }else{// 지수가 홀수라면
        return t * t % c * a % c; 
    }
}

int main(){

    long long a, b, c;
    
    cin >> a >> b >> c;

    cout << divide(a,b,c);

    return 0;
}

자료형은 long long으로 그리고 재귀함수를 너무 많이 쓰지 않도록 저장하고 호출하는 식으로 작성했다.

감사합니다.