C# 백준 11051 이항 계수 2 (페르마의 소정리, 분할 정복 알고리즘)

11051번: 이항 계수 2

IDEA

이항 계수를 구하는 문제다. 간단한 다음 공식을 사용하면 바로 해결 가능하다.

 

 

그런데 여기서 간단하지 않은 것은 주어진 N의 최댓값이 1,000이다. 20!만 계산해도 long의 표현 범위를 넘어가버린다. 그래서 이 문제에도 분할 정복을 사용해야한다. 그리고 값을 10,007로 나눈 나머지를 출력해야한다. 연산을 모두 끝내고 한꺼번에 나머지를 출력하기엔 너무 큰 숫자를 처리하기 어려울 것 같다. 모듈러 연산을 이용하면 좋겠지만 나눗셈에 대한 모듈러 연산은 없다.

 

 

페르마의 소정리에 따르면 어떤 수 a가 정수이고 p가 소수일 때 다음이 성립한다.

 

 

a가 0이 아닐 때 양변을 a로 나누어준다.

 

 

좌변을 다시 정리한다.

 

 

이렇게 정수 a의 모듈러 연산에 대한 역원을 구할 수 있다. 그럼 원식을 이렇게 다시 정리할 수 있다.

 

 

문제에서 주어진 10,007은 소수이기 때문에 이 방법을 이용해 모듈러 연산의 나눗셈을 거듭제곱으로 바꿀 수 있다.

나머지는 [18291 비요뜨의 징검다리 건너기]의 알고리즘을 그대로 써먹으면 된다.

 

CODE

using System;
class Program
{
    static int N, K;
    static int div = 10007;
    static void Main()
    {
        var nk = Console.ReadLine().Split();
        N = int.Parse(nk[0]); K = int.Parse(nk[1]);
        Console.WriteLine(Fac(N) * Pow(Fac(N - K) * Fac(K) % div, div - 2) % div);
    }
    static int Fac(int f)
    {
        if (f < 2) return 1;
        else return f * Fac(f - 1) % div;
    }						// 팩토리얼 연산은
    						// 배열을 추가해서 중복 연산을 피할 수 있다.
                            			// 그래봤자 눈에 띄는 변화는 없지만
    static int Pow(int b, int e)		// 거듭제곱의 분할 정복
    {
        int res = 1;
        while (e > 0)
        {
            if (e % 2 == 1)
            {
                res *= b;
                res %= div;
                e--;
            }
            b *= b;
            b %= div;
            e >>= 1;
        }
        return res;
    }
}