기본 이론

 

 

큰 자연수 A, B, M에 대해 $ A^{B}\left ( mod M \right ) $의 값을 필요로 하는 문제가 많습니다.

 

이 카테고리에서는 이런 문제를 몇 가지 풀어보려고 합니다.

 

이 글에서는 문제를 풀기 이전에 주요 개념을 간략하게 설명해보도록 하겠습니다.

 

---

1. Exponentiation By Squaring

 

$x^{y}$를 분할 정복을 이용하여 빠르게 구하는 기법입니다.

 

이때 y의 이진수 꼴을 쓰는 경우 Binary Exponentiation이라고도 합니다.

 

실제 코드 전에 간단히 예시를 보겠습니다.

 

(10^13) = (10^8) * (10^4) * (10^1)

13 = 1101

8 =  1000
4 =  0100
1 =  0001

 

구조가 보이나요?

 

$x^{y}$에서 y를 binary로 나타낸 것을 $y=d_{k}d_{k-1} \cdots d_{1}d_{0}$ 라고 할 때,

$$ x^{y} = \prod_{i=0}^{k} x^{ (2^{i} \times d_{i}) } = \prod_{d_{i}=1} x^{2^{i}}$$

입니다.

 

이때 $x^{2^{i}}$ 간에는 다음 점화식이 성립합니다.

$$ x^{2^{i+1}} = \left ( x^{2^{i}} \right )^{2} $$

 

따라서 $x^{y}$를 다음과 같이 구현할 수 있습니다.

 

long long power_modular (long long x, long long y) {
	// return x ^ y
	long long result = 1; // 1 = x ^ 0
	while (y > 0) {
		if (y & 1) {
			result *= x;
		}
		x *= x;
		y >>= 1;
	}
	return result;
}

 

long long 타입의 변수 y는 이미 메모리 상에 이진수의 형태로 저장되어 있으므로, 비트연산자 >>와 &, 또는 산술연산자 %와 /를 이용해도 원하는 결과를 얻을 수 있습니다. 문자열로 저장된 p진수 y의 경우 각 자릿수마다 x를 p제곱해주어야 하는 등 추가 공정이 필요합니다.

 

이렇게 구현한 함수 power_modular은 y가 p진법으로 저장되었을 때 $O\left ( \log_{p} y \right ) = O\left ( \log y \right )$의 복잡도를 갖게 될 것입니다.

---

2. 곱셈 과정에서의 오버플로우 방지

 

1에서 구현한 코드는 오버플로우가 일어나기 매우 쉽습니다.

 

따라서 많은 문제에서는 $x^{y}$를 적당한 수 M으로 나눈 나머지를 출력하라고 합니다.

 

합동식에서 성립하는 다음 성질을 이용하면 이를 쉽게 접근할 수 있습니다.

 

$$ a \times b = (a \; \textrm{mod} \; M) \times (b \; \textrm{mod} \; M) \;\; (\textrm{mod} \; M) $$

 

이를 이용하여 1의 코드를 조금 수정해보겠습니다.

 

long long power_modular (long long x, long long y, long long M) {
	// return x ^ y mod M
	long long result = 1; // 1 = x ^ 0
	while (y > 0) {
		if (y & 1) {
			result = result * x % M;
		}
		x = x * x % M;
		y >>= 1;
	}
	return result;
}

 

그러나 이 역시 오버플로우가 일어나기 쉽습니다.

 

그 이유는 6, 8번째 줄의 곱셈 연산 때문입니다.

 

따라서 $M \geq \sqrt{2^{63} - 1}$ 일 경우, 오버플로우가 일어나지 않도록 두 수를 곱해주는 함수가 필요합니다.

 

다음 코드는 Exponentiation By Squaring과 같은 원리로 작동합니다. (연산자 우선순위에 의해 괄호가 생겼음에 주의해주세요.)

 

long long multiply_modular (long long x, long long y, long long M) {
	// x * y (mod M)
	long long result = 0;
	while (y > 0) {
		if (y & 1) {
			result = (result + x) % M;
		}
		x = (x + x) % M;
		y >>= 1;
	}
	return result;
}

 

---

3. 오버플로우를 피하는 power_modular 함수

 

이제 multiply_modular을 이용하여, power_modular함수를 수정해보겠습니다.

 

2번의 multiply_modular을 $log y$ 번 호출하게 되므로, 복잡도는 $O\left ( log^{2}y \right )$ 가 됩니다.

 

long long multiply_modular (long long x, long long y, long long M) { // x * y (mod M)
	long long result = 0;
	while (y > 0) {
		if (y & 1) {
			result = (result + x) % M;
		}
		x = (x + x) % M;
		y >>= 1;
	}
	return result;
}

long long power_modular (long long x, long long y, long long M) { // x ^ y (mod M)
	long long result = 1;
	while (y > 0) {
		if (y & 1) {
			result = multiply_modular (result, x, M);
		}
		x = multiply_modular (x, x, M);
		y >>= 1;
	}
	return result;
}

 

---

 

4. 덧셈 과정에서의 오버플로우 방지

 

위 코드는 많은 상황에서 잘 작동하지만, M이 $2^{62}$ 이상으로 커지는 순간 오버플로우가 발생할 수 있습니다.

 

그 이유는 long long이 최대 $2^{63} - 1$ 까지 지원하기 때문입니다. 

 

그로 인해 multiply_modular 함수 내에서 result와 x가 $2^{62}$ 이상으로 커지게 되더라도 (modulo 연산 시행 전에)

 

오버플로우를 막을 수 있는 새로운 함수가 필요하게 됩니다.

 

이는 다음과 같이 구현할 수 있습니다.

 

long long add_modular (long long x, long long y, long long M) { // x + y (mod M)
	if (x >= M - y || y >= M - x) {
		return (x - M) + y;
	}
	else {
		return x + y;
	}
}

 

if문의 조건은 결국 $x + y\geq M$ 와 동치입니다.

 

이 경우, 미리 M을 빼주고 다시 y를 더합니다. 합동식의 성질에 따라 이는 나머지에 영향을 끼치지 않습니다.

 

그러나 이 코드가 verbose하게 느껴진다면, 다음을 쓸 수 있습니다. 두 방식 모두 $O(1)$이므로 시간 복잡도에 영향은 없습니다.

 

long long add_modular (long long x, long long y, long long M) {
	// x + y (mod M)
	return (x - M) + y;
}

 

따라서 최종적으로, 다음과 같이 power_modular함수를 구현하였습니다.

 

long long add_modular (long long x, long long y, long long M) {
	// x + y (mod M)
	return (x - M) + y;
}

long long multiply_modular (long long x, long long y, long long M) {
	// x * y (mod M)
	// assume x , y < M
	long long result = 0;
	while (y > 0) {
		if (y & 1) {
			result = add_modular (result, x, M);
		}
		x = add_modular (x, x, M);
		y >>= 1;
	}
	return result;
}

long long power_modular (long long x, long long y, long long M) {
	// x ^ y (mod M)
	// assume x < M
	long long result = 1;
	while (y > 0) {
		if (y & 1) {
			result = multiply_modular (result, x, M);
		}
		x = multiply_modular (x, x, M);
		y >>= 1;
	}
	return result;
}

---

여기서 소개한 함수 중에, add_modular, multiply_modular 함수는 M의 범위에 따라선 굳이 구현하지 않아도 충분합니다.

 

마지막으로, __int128 을 지원하는 환경에서는 위 제한을 좀 더 피해갈 수 있을 것입니다.

 

예를 들어 다음과 같이 쓸 수 있습니다.

 

long long power_modular (long long x, long long y, long long M) {
	// x ^ y (mod M)
	long long result = 1;
	while (y > 0) {
		if (y & 1) {
			result = (__int128)result * x % M;
		}
		x = (__int128)x * x % M;
		y >>= 1;
	}
	return result;
}

 

이런 casting이 싫은 경우, x와 M을 미리 __int128 로 설정하는 방법도 있습니다.