Lucas Theorem : 뤼카의 정리

Lucas Theorem : 뤼카 정리는 음이 아닌 정수 n, k 소수 p에 대해   를 구하는  효율적인 계산 방식을 제공하는 정리입니다.

이항계수는  이므로 n과 k가 크면 계산하기가 상당히 부담스럽습니다. 식에 Factiorial이 포함되기 때문에

숫자가 조금만 커져도 int나 long long 자료형에 담을 수 없어 

n!과 k!, (n-k)!을 다 계산한 후 나누어주는 방식을 취할 수 없습니다.

따라서 이항 계수를 구할 때 다음 정리를 이용해서 

배열에서 파스칼 삼각형을 구성하거나 메모제이션방식으로 얻게 됩니다. 

그러나 위 방식으로 다음 문제처럼   

(M은 소수) n이 매우 큰 문제에 대해 접근하면  엄청난 메모리 사용과 연산량으로 인해 해결할 수 없습니다.

위 문제는 뤼카의 정리를 이용해서 해결할 수 있습니다. 

Lucas Theorem : 뤼카의 정리

---

위키에 있는 내용을 부연설명 하겠습니다.

뤼카 정리는 음이 아닌 정수 n, k, 소수 p에 대해서  

다음과 같이  n과 k를 p진법 전개식으로 나타냈을 때

다음 합동식이 성립하는 것에 대한 정리입니다.

예시

---

이제 를 뤼카의 정리를 이용해서 구해보겠습니다. 

먼저 다음과 같이 1432와 342을 7진법 전개식으로 나타내야 합니다. 

따라서 다음과 같이 나타낼 수 있습니다. 

이때  이면  으로 취급합니다. (그 이유는 아래 증명에서 확인할 수 있습니다.)

따라서  의 값이 0임을 얻을 수 있습니다. 정말 0일까요?

메모제이션으로 이항계수를 구하는 아래 코드를 작성하여 확인 해 보았습니다. 한번 해보시면 정말로 0이 나옵니다!

증명

---

음이 아닌 정수 n, k 소수 p에 대해서  다음과 같이  n을 p진법 전개식으로 나타냈다고 합시다.

 

먼저 이항정리에 의해 좌변을 다음과 같이 전개할 수 있습니다.

따라서 이 성립합니다.

이제 이를 이용해서 뤼카의 정리를 증명할 수 있습니다.

위 식을 전개했을 때 차수가 k인 가 되기 위해서  가 

곱해진 횟수를 이라 합시다.

그러면 를 만족해야하며

의 계수는 이 됩니다. (다음 계수는 기본적인 이항계수 유도 원리로 도출되었습니다.)

따라서  

이 성립합니다.   

그러므로 임을 증명할 수 있습니다.

관련 문제

---

이제 위에서 언급한 뤼카의 정리를 대놓고 적용해볼 수 있는 백준온라인저지 11402번 이항계수4 문제에 대한 

코드를 작성해보겠습니다. 

뤼카의 정리를 직관적으로 그대로 코드로 옮겨보았습니다.

이제 위 코드 보다 훨씬 간결하고 짧게 짤 수 있는 방법이 있어서 소개합니다.

이제 뤼카의 정리가 숨어 있는 문제를 소개합니다.

1. ACM ICPC Asia Kuala Lumpur Regional Contest 2014 K번 문제 - 이 문제는 백준온라인저지 10370번  Ball 에서 채점받으실 수 있습니다. 

2. ACM ICPC Jakarta 2014 Punching Robot 문제