[백준] 알고리즘 C++ 1629번 - 곱셈문제

문제

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

1629번: 곱셈

소스코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <math.h>
#include <stack>
#include <limits.h>
using namespace std;
long long a, b, c;
long long bs(long long num, long long e) {
    if (e == 0) return 1;
    if (e == 1) return num % c;
    long long n2 = bs(num, e / 2);

    if (e % 2 == 0) {
        return n2 * n2 % c;
    }
    else {
        return n2 * n2 % c * num % c;
    }
}
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    cin >> a >> b >> c;
    cout << bs(a, b);

}

해설

무지성으로 POW를 사용하여 정답을 도출 할 수 있는가? 할 수 없다.

그렇다면 우리는 지수법칙과 모듈러 법칙을 알아야한다.

1. 지수법칙

a^6 = a^3*a^3

이런식으로 지수들을 더하기로 나눠줄 수 있다. 즉 분할정복을 이용하여 지수들을 2씩 계속해서 나눠준다.

결국 지수가 1이 되었을 경우 a*a로 되므로 a^2승을 표현할 수 있다.

 

2. 모듈러 법칙

(a x b) mod c = (a mod c x b mod c) mod c