백준 1629, 곱셉(C, C++)

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

1629번: 곱셈

#include<iostream>

int C;

long pow(long A, long B){
    if(B == 1){
        return A % C;
    }

    long temp = pow(A, B/2); 

    //짝수인 경우

    if(B % 2 == 0){
        return (temp * temp) % C;
    }
    
    //홀수인 경우

    if(B % 2 == 1){
        return (temp * temp) % C * A % C;
    }
}

using namespace std;
int main(){

    long A;
    long B;

    cin >> A >> B >> C;

    

    cout<<pow(A, B);



    return 0;
}

 

이 문제에서는 간단하게 생각하면 틀리게 되어있습니다.

일정 크기 이상의 A가 B번만큼 곱하게 되면 2147483647 을 넘어가게 되어 오버플로가 발생합니다.

이 수는 231 - 1와 같습니다.

 

지수의 성질을 이용해야 하는데,

짝수인 부분은 절반으로 나누고 홀수는 지수가 +1이 처리되었다고 생각하면 됩니다

예시로 2^12 = 2^6 * 2^6 = 2^3 * 2^3 * 2^3 * 2^3 = 2^1 *2^2 * 2^1 *2^2 * 2^1 *2^2 * 2^1 *2^2 *2^1 *2^1

 

모듈러 산술도 이용해야합니다.

https://sskl660.tistory.com/75

모듈러 산술(Modular Arithmetic)