모듈러 연산에서 조합 계산하기 - 페르마의 소정리와 빠른 제곱법의 활용

1. 문제 배경: 조합 계산과 모듈러 연산

조합 계산에서 $C(n, r) = {n! \over r! \times (n-r)!}$ 을 계산하려면 나눗셈이 필요합니다. 하지만 모듈러 연산에서는 일반적인 나눗셈을 할 수 없기 때문에, 모듈러 역원을 사용하여 나눗셈을 곱셈으로 변환해야 합니다.

이를 위해 모듈러 역원과 페르마의 소정리를 이용합니다.

2. 모듈러 역원(modular inverse)이란?

모듈러 연산에서 어떤 수 ( a )의 모듈러 역원 ( a^{-1} )은 다음 식을 만족하는 값입니다.

즉, $a$에 $a^{-1}$ 을 곱했을 때 마치 나누기 연산을 한 것과 같은 효과를 얻습니다. 모듈러 역원을 구하면 모듈러 연산에서 나눗셈을 구현할 수 있습니다.

3. 페르마의 소정리와 모듈러 역원 구하기

페르마의 소정리에 따르면 소수 $p\\$에 대해 $a^{p-1} \equiv 1 \mod p$입니다.
따라서 $a^{p-2}$는 $a$ 의 모듈러 역원이 됩니다. 이때 $MOD$가 소수라면 다음과 같이 모듈러 역원을 구할 수 있습니다.

즉, 조합 계산에서 $C(n, r) = {n! \over r! \times (n-r)!}$ 을 모듈러 연산으로 계산할 때,

와 같이 나눗셈을 곱셈으로 변환할 수 있습니다.

4. 빠른 제곱법으로 효율적으로 역원 계산하기

$a^{MOD-2}$ 를 계산할 때 반복적인 곱셈을 사용하면 시간 복잡도가 너무 커지므로, 빠른 제곱법을 사용하여 효율적으로 계산합니다. 이를 통해 지수 계산을 $O(\log b)$ 시간에 수행할 수 있습니다.

5. 구현 코드

static int MOD = 1234567891;

static long factorial(int n) {
    long result = 1;
    for (int i = 2; i <= n; i++) {
        result = (result * i) % MOD;
    }
    return result;
}

static long modInverse(long a) {
    return power(a, MOD - 2);  // a의 모듈러 역원 계산
}

static long power(long a, int b) {
    long result = 1;

    while (b > 0) {
        if (b % 2 == 1) {
            result = (result * a) % MOD;
        }
        a = (a * a) % MOD;
        b /= 2;
    }

    return result;
}

• factorial(): $n!$ 을 모듈러 연산으로 계산합니다.
• modInverse(): $a$ 의 모듈러 역원을 구합니다.
• power(): 빠른 제곱법으로 $a^{MOD-2}$ 를 계산하여 역원을 구합니다.

---

요약

모듈러 연산에서 나눗셈을 처리하려면 모듈러 역원이 필요합니다. 이를 위해 페르마의 소정리를 적용하여 $a^{MOD-2} \mod MOD$로 역원을 구할 수 있으며, 빠른 제곱법을 사용해 효율적으로 계산할 수 있습니다. 이 방법은 조합 계산에서 큰 수를 안전하게 다루는 데 매우 유용합니다.

관련 문제

• 백준 이항계수 3