모듈러 나눗셈 연산 처리하기

프로그래밍 문제에서 가끔 이런 연산을 요구하는 문제들이 있다.

(N/K) % MOD

N과 K의 값이 작으면 N과 K의 값을 먼저 계산 하고 나서 모듈러 연산을 취해주면 문제가 없다.

하지만 N과 K값이 64bit 이상으로 변수에 넣을 크기를 초과하는 경우 앞의 나눗셈 계산은 정상적인 값을 내놓지 않을 것이고 모듈러 연산은 정상이 아닌 값을 받아 처리해 결론적으로 잘못된 값을 낸다.

주로 N과 K를 팩토리얼로 받는 조합의 경우의 수를 구할 때 난감하다 -> nCr % MOD 인 경우

이런 경우를 해결 하기 위해 모듈러 연산의 나눗셈을 계산하는 특별한 방법이 존재한다.

모듈러 연산에서 나눗셈 N/K는 K로 나누는 대신에 K의 곱셈 역원(multiple inverse)를 곱하는 방식으로 이뤄진다. 곱셈 역원은 MOD(모듈러 연산으로 나누는 값)과 나누는 값 K가 서로소일때만 존재한다. 곱셈 역원을 구하는 방법은 다음과 같다.

modInv(K, MOD) = K^(MOD-2)%MOD

곱셈역원을 이용해 나눗셈을 다음과 같이 정리 할 수 있다.

(N/K) % MOD = (N * modInv(K, MOD-2))%MOD    (페르마의 소정리라고도 한다. 이해하긴 어려우니 일단 외우자)

하지만 여기서 MOD 값이 매우 크다면 (대부분 문제에서 1,000,000,007을 잡는다) K^(MOD-2) 까지 곱하는데 시간이 오래 소요될것이다. 그래서 이런 경우 최적화 할 방법도 같이 기억해두면 좋다.

1. 가장 간단한 방법은 지수의 제곱승을 이용하는 방법이다(이 테크닉의 정확한 이름을 모르겠다)

예를들어 A^5 을 구한다고 한다면, A를 다섯번 곱해 A*A*A*A*A 구하는 방법이 있지만 다른 방법은 A*(A^2)*(A^2) 로 구하는 방법도 있다. A^2를 한 번만 구하면 되므로 기존 방법보다 곱셈의 횟수를 줄일 수 있다. 시간 복잡도는 O(logMOD)이다.

코드는 이렇다

 
long long modInv(long long a, int M) {
	if (M == 1)
		return a;
	if (M == 0)
		return 1;

	long long  tmp = modInv(a, M / 2);
	if (M % 2)
		return (long long)((long long)((tmp*tmp) % MOD)*a) % MOD;
	else
		return (long long)(tmp*tmp) % MOD;
}

2. O(logMOD)말고 O(1)에 해결하는 방법도 있다고 한다. 이건 이 포스트를 참고하자. 나도 증명은 잘 모르겠다.

http://koosaga.myungwoo.kr/entry/%EC%9D%B4%ED%95%AD%EA%B3%84%EC%88%98-nCr-mod-p-%EA%B3%84%EC%82%B0%ED%95%98%EA%B8%B0

위 포스트 글을 코드로 옮기면 이렇다.

 
	for (int i = 2; i <= MAX; i++) {
		inv[i] = (-(MOD / i)*inv[MOD%i] + MOD)%MOD;
		if (inv[i] < 0)
			inv[i] += MOD;
		inc[i] = (inc[i - 1] * inv[i]) % MOD; // 팩토리얼 곱셈역원 계산
	}

모듈러 연산은 진짜 왠만하면 피하고 싶은 문제인데, 그래도 이번 기회에 테크닉이라도 배워 뒀으니 앞으로 자주 써먹어야겠다.