백준 13172번 Σ [JS 풀이]

최초 업로드 2023-11-20 / 마지막 수정 2023-11-23

문제를 이해하는데 긴 시간이 소요되었다. 풀이는 어렵지 않았으나, modulo 복습과 gcd를 왜 사용하지 않아도 되는지에 대해 기억하기 위해 남긴다.

포인트 1

"소수 모듈러에서만 성립하는 페르마의 소정리에 의해 b^X - 1 ≡ 1 (mod X)가 성립하기에, b^X - 2 ≡ b^-1 (mod X) 역시 성립함을 알 수 있다. 이해를 돕기 위해 X를 11로 두고 Q = 7/3 을 계산해보자. 3^-1 ≡ 4 (mod 11)이므로, Q ≡ 7 × 4 ≡ 6 (mod 11)이다."

위 문구의 단계를 더 잘게 나누어보면 아래와 같다.

\begin{gather} b^{X - 2} ≡ b^{-1} \mod X \\ 3^{11 - 2} ≡ 3^{-1} \mod 11 \\ 3^{11 - 2} \% 11 = 3^{-1} \% 11 \\ 3^{9} \% 11 = 3^{-1} \% 11 \\ 4 = 3^{-1} \% 11 \\ 4 \% 11 = 3^{-1} \% 11 \\ 4 ≡ 3^{-1} \mod 11 \\ \therefore 3^{-1} ≡ 4 \mod 11 \end{gather}

처음에 4가 어디서 나오는지 몰라서 이해가 오래걸렸다. 3^(11-2)를 해준 후에 11로 나머지 연산을 해주면된다.

포인트 2

큰 제곱수는 분할정복으로 O(log(n))으로 풀 수 있음을 알아야한다.

n이 짝수일 경우

$2^n = 2^{n/2}*2^{n/2}$

n이 홀수일 경우

$2^n = 2^{(n-1)/2}*2^{(n-1)/2}*2$

위와 같은 성질을 이용하면 쉽게 풀린다.

포인트 3

1_000_000_007로 나머지를 취할 시, 1_000_000_006 * 1_000_000_006의 상황이 나올 수 있다. 해당 숫자는 JS의 Number의 MAX_SAFE_INTEGER인 천조단위(16자리)를 넘어가게된다. 고로 BigInt를 써야한다는 생각을 해주어야한다.

포인트 4

기약분수 형태로 표현해야한다고 하여 처음에 gcd를 구현했었는데, 다른 풀이들을 보니 gcd를 포함하지 않고도 풀리는 것 같았다. gcd없이 체줄했더니 속도는 480ms => 400ms로 빨리지긴했는데, 왜 정답인지 모르겠어서 직접 고민해보기로 했다. (그 어떤 블로그에서도 설명이 되어있지 않았다.)

이게 말이 되려면 gcd가 어떤 값이어도 항상 정답이 나와야하기 떄문에 예시에 나왔던 3, 7과 mod 11을 이용한 결과와 3*x, 7*x에 mod 11을 이용한 결과가 x가 어떤 값이든 항상 같아야한다는 것이다. 풀어서 이야기하자면, 예시에서는 3, 7, mod 11을 이용해서 6이라는 숫자가 결과로 나왔었다. 기약분수일 필요가 없다면 3 7 이 아니라 6 14 와 같이 분자와 분모에 똑같은 수를 곱한 어떤 수라도 똑같이 6이 나와야한다는 것이다.

직접 계산해보니 신기하게도 $6 = (3^9*7)\%11 = (6^9*14)\%11 = (9^9*21)\%11 = ...$ 이런식으로 계속 이어졌다.

숫자들 내에서 패턴을 찾기 어려워서 수식으로 보기로했다. (9)번 식은 문제에서 주어진, 우리가 코드로 구현한 수식이다. (10)번 식에서는 gcd를 y라고 본 상태이다. b를 b'y으로, a를 a'y로 분리시켰다.

\begin{gather} (b^{X-2} \% X *a) \% X = k \\ ((b'y)^{X-2} \% X *a'y) \% X = k \\ (b'^{X-2}\% X * y^{X-2} \% X *a'y) \% X = k \\ b'^{X-2}\% X * y^{X-2} \% X *a'y \% X = k \\ (b'^{X-2}y^{X-2}a'y) \% X = k \\ (b'^{X-2}a'y^{X-1}) \% X = k \\ b'^{X-2}\% X * a'\% X * y^{X-1}\% X = k \\ b'^{X-2}\% X * a'\% X = k \\ \therefore (b'^{X-2}\% X * a')\% X = k \\ \end{gather}

(11), (12), (13), (14), (15)은 mod의 분배법칙과 mod의 성질을 이용해서 원하는 모양으로 수식을 바꾸어주었다. 가장 큰 핵심은 (16)번 수식에 있는데, $y^{X-1}\% X = 1$ 이 페르마의 소정리에 의해 성립한다. 그래서 해당 부분이 수식에서 사라지게되고, 기약분수의 분모 분자에 어떤 값을 곱하더라도 결과는 동일하다는 결론에 이를 수 있다. 결국, 문제에서 기약분수로 바꾸라고 하는 말 자체는 이해는 도울 수 있지만 실제로는 필요하지 않은 연산이라는 것이다.

JS 풀이

let input = require("fs").readFileSync("/dev/stdin").toString().trim();
//let input = `1
//6 14`

input = input.split("\n");
let n = Number(input[0]);
const div = 1_000_000_007n;

const expectations = [];

function get_pow(val, pow) {
  if (pow === 1n) {
    return val;
  }

  if (pow % 2n === 1n) {
    const temp = get_pow(val, (pow - 1n) / 2n) % div;
    return (temp * temp * (val % div)) % div;
  } else {
    const temp = get_pow(val, pow / 2n) % div;
    return (temp * temp) % div;
  }
}

for (let i = 1; i < n + 1; i++) {
  const [side_cnt, sum_of_sides] = input[i].split(" ").map(BigInt);
  const b_inv = get_pow(side_cnt, div - 2n);
  let expectation = (sum_of_sides * b_inv) % div;
  expectations.push(expectation);
}

let sum = 0n;
expectations.forEach((exp) => {
  sum = (sum + exp) % div;
});
console.log(sum.toString());