문제

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

풀이

시간제한이 없다면 매우 쉬운 문제다.
(A ^ B) % C를 구하면 되는 문제인데, 이 식대로 정직하게 계산한다면 최악의 경우인 B가 2147483647이면 0.5초의 시간 제한을 지키지 못한다.

이 문제는 특정 공식을 알고있어야 풀리는 문제다. 바로 모듈러 연산의 분배 법칙인데 이 법칙은 아래와 같다.

(A x B) % C = ((A % C) x (B % C)) % C

이 식을 이 문제에 어떻게 적용할 수 있을까 생각해보자.

우리가 구해야하는건 (A ^ B) % C 라고 했다. 이 식을 풀어서 쓰면 (A x A x ... x A) % C 와 같다(곱해지는 A는 B개). 저 분배 법칙을 (A x (A x A x ... x A)) % C = ((A % C) x ((A x A x ... x A) % C)) % C 이런식으로 사용하면 시간단축면에서 의미가 없다. 이걸 (A^(B/2) * A^(B/2)) % C 이런식으로 사용해야 기하급수로 시간이 단축하게 된다. 이해가 어렵다면 아래 그림을 살펴보자.

따라서 저 분배 법칙을 기하 급수로 감소하게 사용하면 간단하게 답을 구할 수 있다.

BigInt

이 문제를 풀 때 주의해야할 점이 있다.

위 방법대로 한다면 재귀를 사용하게 되는데, 만약 C가 2^31 - 1이고 A가 2^31 - 2라면 ((A % C) x (B % C))이 식을 계산하게 될 경우 계산 값이 거의 2^62가 된다.

js의 int 자료형(Number)의 최댓값은 2^53 - 1 이므로 int의 범위를 늘려주지 않으면 오버플로우가 발생한다.

이때 BigInt 자료형을 사용해서 number의 2^53 - 1보다 큰 범위의 정수를 저장하여 오버플로우를 해결할 수 있다.

사용법은 단순하게 const num = BigInt(5)처럼 사용하면 num의 범위가 BigInt의 범위를 갖게 된다.

그리고 BigInt 자료형과 Number 자료형은 서로 비교할 수 없으므로 비교할 수도 BigInt 자료형으로 바꿔야한다.

짝수, 홀수

그리고 B가 홀수인 경우 (A^(B/2) * A^(B/2)) % C 이런식으로 나눌 수 없다. 그래서 홀수면 (A^(B-1/2) * A^(B-1/2) * A) % C 의 형태로 A를 따로 하나 떼어내서 계산하면 된다.

풀이 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [A, B, C] = input[0].split(' ').map(BigInt);

const getRest = (a, b, c) => {
	// 더 이상 나눌 수 없다면
	if (b === BigInt(1)) return a % c;

	if (b % BigInt(2) === BigInt(0)) {
		// b가 짝수인 경우
		return f(a, b / BigInt(2), c) ** BigInt(2) % c;
	} else {
		// b가 홀수인 경우, 
		return (f(a, (b - BigInt(1)) / BigInt(2), c) ** BigInt(2) * a) % c;
	}
};

const answer = getRest(A, B, C).toString();

console.log(answer);

결과

120ms 나왔다.

설명에 오류가 있거나 이해가 어려운 부분이 있으면 댓글이나 이메일(pigkill40@naver.com)로 문의해 주시면 도움을 드리겠습니다.