백준 node.js 1629번 곱셈 JavaScript JS

1629번: 곱셈

1. (A*B)%C = (A%C) * (B%C) % C 라는 모듈러 산술을 이용하여 문제를 풀 수 있습니다.
2. 아래 주석을 확인해 주세요

문제 풀이

et fs = require('fs');
let [A,B,C] = fs.readFileSync('/dev/stdin').toString().trim().split(" ").map(BigInt)

/*
(A*B)%C = (A%C) * (B%C) % C

1. 짝수일 때 (A^B)%C = (A^(B/2) * A^(B/2)) % C
            = (A^(B/2)%C * A^(B/2)%C) % C
2. 홀수일 때 (A^B)%C = (A^(B/2)) * A^(B/2)) * A) % C
            = (A^Math.floor(B/2)%C * A^Math.floor(B/2)%C * A%C) % C
*/

function solution(B) {
  if(B === 1n){
    return A%C
  }
  let temp = solution(B/2n)
  if(B % 2n === 0n){
    return temp * temp % C
  }else{
	//BigInt에서는 소숫점이 없다. ex)BigInt(11)/BigInt(2) = 5n (5.5n이 아니다)
    return temp * temp * A % C
  }
}
console.log(Number(solution(B)))