[백준] 1629번: 곱셈

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

입출력 예제

풀이

const fs = require('fs');
const [a, b, c] = fs.readFileSync('/dev/stdin').toString().trim().split(' ').map(BigInt);

console.log(pow(b).toString());

function pow(b) {
    if (b === 1n) return a % c;
    let k = pow(b / 2n);

    if (b % 2n === 1n) return (k * k * a) % c;
    else return (k * k) % c;
}

a b c 의 최대 값은 21억이므로, for문을 사용하여 풀이하면
시간 복잡도 O(n) 으로 시간초과>가 난다.

따라서 분할정복법으로 풀이했다.
b가 짝수일 경우,
a ^ b = (a ^ (b/2)) * (a ^ (b/2))

b가 홀수일 경우,
a ^ b = (a ^ (b/2)) * (a ^ (b/2)) * a

따라서 b/2 제곱한 값을 만들어서 사용한다.
제곱 값은 제귀함수로 만들어 낸다.