백준 1629번 곱셈 (C++)

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

1629번: 곱셈

 

A^B mod m을 연산하는 프로그램을 작성하는 문제이다.

 

수의 범위가 20억까지 가능하기 때문에 long long 타입을 활용한 것 이외에 재귀를 진행할 때도 아이디어가 하나 필요했다.

 

B가 홀수냐 짝수냐에 따라서 경우를 나눠줬다.

 

재귀의 base condition은 B가 0일 때 1을 반환하는 것이 된다.

 

또한 overflow를 방지하기 위해 계산하는 중간중간에 modular 연산을 수행해줄 필요가 있다.

 

XYmodM = (XmodM * YmodM) mod M 인 것을 이용하면 되겠다.

 

지수가 홀수인 경우, 계산 이후에 a를 한 번 더 곱해줘야 하고, 이 과정에서 modular 연산을 한번 더 수행해줘야 한다.

 

#include<iostream>
using namespace std;
typedef long long ll;

ll POW(ll a, ll b, ll m){
    if(b == 0) return 1;
    ll val = POW(a, b/2, m);
    val = val * val % m;
    
    //b가 짝수, 홀수인 경우 나눠서 처리
    if(b % 2 == 0) return val;
    else
        return (val * a) % m;
    
}

int main(void){
    int a, b, m;
    cin >> a >> b >> m;
    cout << POW(a, b, m);
    return 0;
}