백준 1629: 곱셈 [C++]

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

 

 

큰 수의 곱셈 문제가 있을 때 떠올리면 좋은 건 분할정복과 비트마스킹이다.

a를 b번 곱할 때 반복문으로 b번 곱하는 것이 아니라, 지수를 반으로 나눠서 거듭제곱하는 방식이다. 물론 이때 지수가 짝수이면 그냥 반 갈라도 되지만 지수가 홀수이면 1을 하나 빼서 나눈 뒤 마지막에 한번 더 곱해줘야 한다.

처음에는 그냥 비트마스킹만 생각했는데 그럼 2의 거듭제곱만으로 계산해야 하니 귀찮았다..

 

단 숫자가 아주 커질 수 있기 때문에 그냥 계산하면 오류가 날 수 있으므로 계산 과정에서 매번 c로 나눈 나머지를 사용하도록 해서 오버플로가 나지 않게 해준다.

 

b & 1 이라는건 비트마스킹에서 첫번째 비트가 1인 수와 and를 했을 때 true 즉 0이 아니라는 뜻으로, b의 1번째 비트가 1이라는 의미이다. 이는 곧 b가 홀수임을 의미한다.

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

ll multi(ll a, ll b, ll c){
    ll result = 1;
    a %= c;
    while(b){
        if (b&1){ //b가 홀수면
            result = (result * a) % c;
        }
        a = (a*a)%c;
        b = b >> 1; //b를 반으로 나눔
    }
    return result;
}

int main() {
    ll a, b, c;
    cin >> a >> b >> c;
    //a를 b번 곱한 수를 c로 나눈 나머지
    ll result = multi(a, b,c );
    cout << result;
    return 0;
}