뤼카의 정리 - Lucas' Theorem

개요

알고리즘 관련 글을 오랜만에 쓰는 거 같은데 공부하고 싶은 수학 알고리즘들이 많아서 하나 잡고 정리를 했습니다. 많이 본 것들 중 하나가 바로 '뤼카의 정리'입니다. 조합에 있어서 조합을 소수 p 로 나눌 때 나머지를 빠르게 구할 수 있는 방법입니다.

 

 

간단 기본 지식

오랜만에 수식들을 봐서 그런지 용어들이 익숙하지 않아 이해하는데 시간이 좀 걸렸습니다. 일단 조합은 확률과 통계에서 많이 보이던 아래 식을 의미합니다.

출처 : 아주 자세한 나무위키

다른 말로 이항계수라고도 합니다.

 

그리고 뤼카의 정리는 이런 합동식으로 만들어지게 됩니다.

라고 하는데 여기서 '합동식'은 

이런 식들을 의미하는데 다른 식으로 이렇게 표현합니다.

말로 풀어보면 'a를 m으로 나눌 때 나머지가 b'라는 뜻입니다. 다른 이야기들이 있는데 일단 넘어가자고요.

 

 

본격 뤼카의 정리

이제 기본 지식을 봤으니 본론을 보면 됩니다. 뤼카의 정리는 아래 의도로 사용하게 됩니다.

조합에 있어서 조합을 소수 p로 나눌 때 나머지를 빠르게 구할 수 있는 방법

일단 수학을 좋아하지는 않지만 수식 좋아하는 사람들은 바로 이해할 수 있는 수식이 있습니다.

즉 mCn을 소수 p로 나눈 결과는 아래 식이라는 것이죠.

이 식을 이해하는데 오래 걸렸는데 이 부분의 경우 아래로 이해하면 편합니다.

m, n을 p 진수로 변경한 뒤 p 진수의 각 자릿수를 조합하면 된다

라는 뜻입니다.

 

아래 예시로 백준 문제에 있는 조합을 한번 보겠습니다. 30C3을 3으로 나눈 나머지를 알아내라는 문제입니다.

일단 30을 3진수로 변경하면 1010(3)이고 3은 10(3)이 됩니다.

30	1	0	1	0
3	0	0	1	0

이제 각 자릿수에 대해서 조합을 해 주면 아래 식이 되는 것입니다.

이제 30C3의 조합을 구하는 것보다는 한결 쉬워졌습니다. 정답은 1이 되는 것이죠.

 

 

주의점

간단한 주의점들만 알아보고 가겠습니다.

• 뤼카의 정리는 조합에 있어서 소수로 나눌 때 사용하는 알고리즘입니다.
• 만일 nCr에서 r 이 더 커지면 이때 결괏값은 0이 됩니다.

 

 

증명은 없고 코드는 있습니다.

저희는 프로그래머니깐 이런 규칙이 있고 증명이 따로 있으면 증명은 취미 영역이라 생각이 됩니다. 보실 분들은 아래 링크들을 보시면 될 것 같고 일단 C++로 작성한 코드를 먼저 보겠습니다.

vector<int> GetNotationNumber(ll number, int notation){
    vector<int> answer;
    while (number > 0){
        answer.push_back(number % notation);
        number /= notation;
    }
    return answer;
}

일단 p 진수로 변경하는 코드입니다. 결괏값의 각 자릿수로 이항계수를 만드니 리턴값은 vector<int>가 되겠습니다.

using ll = long long;
const int MAXNUM = 2001;

ll BC[MAXNUM][MAXNUM];
//...
ll BinomialCoefficient(int n, int k){
    if(n < k)       return 0;
    if(n / 2 < k)   k = n - k;

    ll& result = BC[n][k];
    if(result != -1)    return result;
    if(k == 0)          return result = 1;
    if(k == 1)          return result = n;

    return result = (BinomialCoefficient(n-1, k-1) + BinomialCoefficient(n-1, k)) % m;
}

이후 이항 계수를 구하는 함수를 준비해 줍니다. 여기서 수식의 p는 m이 되었습니다. 또한 이항계수를 구하는 과정에 있어서 BC 배열을 사용하는데 이는 한번 구해둔 조합을 저장해 이후 사용할 경우 배열의 값을 사용하는 것입니다.

cin >> n >> k >> m;

ll answer = 1;

auto nToMNotation{ GetNotationNumber(n, m) };
auto kToMNotation{ GetNotationNumber(k, m) };

auto minSize{ min(nToMNotation.size(), kToMNotation.size()) };
int forLoopIndex = static_cast<int>(minSize);

for(int i = 0; i < forLoopIndex; i++){
    answer *= BinomialCoefficient(nToMNotation[i], kToMNotation[i]);
    answer %= m;
}

그러면 조합을 구할 땐 이런 느낌의 식이 나오게 될 겁니다. 한쪽의 p 진수가 많이 나올 수도 있으니 minIndex를 구한 뒤 사용해줘야 합니다.

 

 

예시 문제

백준의 대표 문제입니다.

11402번: 이항 계수 4

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;
using ll = long long;
const int MAXNUM = 2001;

ll n, k, m;
ll BC[MAXNUM][MAXNUM];

vector<int> GetNotationNumber(ll number, int notation){
    vector<int> answer;
    while (number > 0){
        answer.push_back(number % notation);
        number /= notation;
    }
    return answer;
}

ll BinomialCoefficient(int n, int k){
    if(n < k)       return 0;
    if(n / 2 < k)   k = n - k;

    ll& result = BC[n][k];
    if(result != -1)    return result;
    if(k == 0)          return result = 1;
    if(k == 1)          return result = n;

    return result = (BinomialCoefficient(n-1, k-1) + BinomialCoefficient(n-1, k)) % m;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    memset(BC, -1, sizeof(BC));

    cin >> n >> k >> m;

    ll answer = 1;

    auto nToMNotation{ GetNotationNumber(n, m) };
    auto kToMNotation{ GetNotationNumber(k, m) };

    auto minSize{ min(nToMNotation.size(), kToMNotation.size()) };
    int forLoopIndex = static_cast<int>(minSize);

    for(int i = 0; i < forLoopIndex; i++){
        answer *= BinomialCoefficient(nToMNotation[i], kToMNotation[i]);
        answer %= m;
    }

    cout << answer << '\n';
}

 

참고 링크

조합 - 나무위키

뤼카의 정리 - 위키백과, 우리 모두의 백과사전