백준 [nodejs] > 1629번 곱셈

 

 

문제

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

 

풀이

js에서 BigInt를 많이 다뤄보지 않아서 굉장히 생소해서 많이 버벅 거렸다.

BigInt는 2^53-1를 js 내에서 다룰 수 있는 내장객체이다. 이 문제를 풀기 위해서는 해당 객체를 이용해야 한다. 왜냐하면 

주어진 A,B,C 의 범위가 2,147,483,647 이하이기 때문에 2,147,483,647의 제곱승만 되도 이미 BigInt를 다뤄야 한다. 

 

이 문제를 풀기위해서 핵심은 다음과 같다

 

1. (A * B) % C  =  ((A%C) * (B%C))%C 이다

-> 자바스크립트에서 큰숫자의 연산보단 작은숫자의 연산 속도가 훨씬 빠르기 때문에 이를 이용하여 나머지들을 곱하는게 속도차원에서 좋다

 

2. 2^10 을 구하기 위해 2를 10번 곱하기보단 (9번의 연산횟수) 2^5을 구한뒤 2^5를 2개 곱하자! (5번의 연산횟수)

 

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim();

let [A, B, C] = input.split(" ").map((n) => BigInt(n));

let recursive = (pow) => {
    if (pow === 1n) {
        return A % C;
    }
    let newPow = pow / 2n;
    let half = recursive(newPow) % C;

    if (pow % 2n === 0n) {
        return (half * half) % C;
    } else {
        return (half * half * (A % C)) % C;
    }
};

let answer = recursive(B);
console.log(Number(answer));