반응형 이항계수 썸네일형 리스트형 PS를 위한 정수론 - (4) 이항 계수 (nCr mod P) 구하는 다양한 방법 이항 계수 $_{n}C_r$을 소수 $p$로 나눈 나머지를 빠르게 구하는 다양한 방법들을 알아보자. 기본적으로 특정 $n$과 $r$에 대해서 이항 계수 $_{n}C_r$을 구하는 시간은 $O(1)$이 되어야 할 때, 즉, 많은 쿼리가 들어와도 문제가 없는 경우를 고려한다. 지금부터 소개하는 방법들의 시간복잡도는 전처리하는데 필요한 시간을 의미한다. 너무 작은 $n$과 $r$에 대해서 직접 분자와 분모를 모두 곱하는 경우는 생략한다. 1. $O(n^2)$ www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 파스칼의 삼각형을 이용하는 .. PS를 위한 정수론 - (3) 페르마의 소정리와 활용 (이항 계수, 밀러-라빈) [목차] 1. 페르마의 소정리 2. 오일러 정리 3. 활용 1) 이항 계수 nCr 빠르게 구하기 4. 활용 2) 밀러-라빈(Miller-Rabin) 소수 판별법 1. 페르마의 소정리 (Fermat's little theorem) 페르마의 소정리는 다음과 같다. "소수 $p$와 정수 $a$에 대해서 $a^p \equiv a \; (mod\;p)$" 만약 $a$와 $p$가 서로소이면 $a^{p-1} \equiv 1 \; (mod \;p)$ 를 만족한다. 짧지만 생각보다 PS에서 되게 많이 사용되므로 꼭 알아두는 것이 좋다. 증명 과정은 수학적 귀납법을 이용한다. (이 블로그를 참고했다) 먼저, $a$가 $p$ 이상이면, modular의 성질에 의해서 $p$로 나눈 나머지로 계산해도 동일하므로, $0 \leq.. 메모이제이션 (Memoization) 메모이제이션 (Memoization) 이 알고리즘에 대해서는 백준 알고리즘 11051번 (이항 계수 2) 문제를 통해서 학습하게 되었다. 메모이제이션은 동적 계획법 (Dynamic programming)의 핵심 기술이다. (동적 계획법에 대한 설명은 따로 정리를 할 예정이므로 이 게시물에서 개념에 대한 설명은 간단하게 한다.) 우선 해당 문제에 대해서 한번 살펴보자. 다음과 같이 문제가 주어져 있다. 즉, 예를 들어 입력으로 5 2를 입력하게 되면, 10이 출력되어야 한다. 이 알고리즘에 대해 알지 못하거나 익숙하지 않은 사람들은 필자를 포함하여 대부분 위의 식을 이용해서 풀었을 것이다. 즉, 만약 "10 5" 가 입력되었다면, (N = 10, K = 5) 1부터 10까지 곱한 후, 다시 1부터 5까지 .. 이전 1 다음
