멍멍멍

Lucas Theorem : 뤼카 정리는 음이 아닌 정수 n, k 소수 p에 대해 를 구하는 효율적인 계산 방식을 제공하는 정리입니다. 이항계수는 이므로 n과 k가 크면 계산하기가 상당히 부담스럽습니다. 식에 Factiorial이 포함되기 때문에 숫자가 조금만 커져도 int나 long long 자료형에 담을 수 없어 n!과 k!, (n-k)!을 다 계산한 후 나누어주는 방식을 취할 수 없습니다. 따라서 이항 계수를 구할 때 다음 정리를 이용해서 배열에서 파스칼 삼각형을 구성하거나 메모제이션방식으로 얻게 됩니다. 그러나 위 방식으로 다음 문제처럼 (M은 소수) n이 매우 큰 문제에 대해 접근하면 엄청난 메모리 사용과 연산량으로 인해 해결할 수 없습니다. 위 문제는 뤼카의 정리를 이용해서 해결할 수 있습니다..