본문 바로가기
반응형

알고리즘/수학

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..
PS를 위한 정수론 - (2) 유클리드, 확장 유클리드 호제법 [목차] 1. 유클리드 호제법 2. 확장 유클리드 호제법 3. 모듈러(modular) 연산에서의 곱셈의 역원 4. 예시 문제 1. 유클리드 호제법 유클리드 호제법은 정수론을 조금이라도 공부했다면, 혹은 공부하지 않았더라도 충분히 들어봤을 것이다. 유클리드 호제법은 자연수 $a$, $b$ 가 주어졌을 때, $gcd(a, b)$ 즉, $a$와 $b$의 최대 공약수를 구하는 방법이다. $a$를 $b$로 나눈 몫을 $q$라고 하고, 나머지를 $r$이라고 하면 $a = bq + r$ 로 나타난다. 이때, $gcd(a, b) = gcd(b, r)$을 만족한다. 이유는 $gcd(a, b) = g$라고 하면, $g|a$, $g|b$ 를 만족하게 되고, $r = a - bq$이므로 $g|(a - bq) = r$ 을 만족..
PS를 위한 정수론 - (1) 에라토스테네스의 체 활용 기본적인 '에라토스테네스의 체' 개념을 아직 모른다면 wogud6792.tistory.com/46 글을 먼저 읽는 것을 추천한다. 크게 어렵지는 않다. 그렇다면 이제 이 에라토스테네스의 체를 활용하는 여러 가지 방법들을 알아보자. 1. 각 2부터 n까지의 자연수 k에 대해, "k가 갖는 가장 작은 소인수"를 계산하는 방법 이는 사실 매우 간단하다. 에라토스테네스의 체 원리를 생각해보면 현재 수가 아직 걸러지지 않았다면 소수이고, 현재 수의 배수들을 제거해나가는 방식이다. 이때, 제거되는 수는 합성수이고 제일 처음 제거될 때 이용되는 소수가 $k$가 갖는 가장 작은 소인수이다. int prime[1000001]; int main(void) { int N = 1000000; for (int i = 1; i
소수 판별법 - 에라토스테네스의 체, 밀러-라빈(Miller-Rabin) 소수판별법 어떠한 자연수 N이 소수인지를 판별하는 방법은 여러 가지 방법이 있다. 그중에서 너무 난도 높은 것은 제외하고 충분히 PS에서 쓸만한 방법을 알아보자. 우선, N이 소수인지를 판별하는 경우와 N이하의 소수가 몇개있는지, N이하의 소수를 모두 구하는 경우 두가지로 보통 나뉜다. 1. N을 2부터 N-1까지 모두 나누기 소수는 1또는 자기 자신으로만 나누어지기 때문에 위의 방법으로 N이 나누어 떨어지지 않는다면 N은 소수라고 할 수 있다. 만약, N이 어떤 두 수로 나누어진다고 한다면, N = p*q의 형태가 되고, p와 q 둘 중 하나는 반드시 $ \sqrt{N} $의 값 이하일 것이다. 따라서 N-1까지 나눌 필요는 없고, $ \sqrt{N} $까지만 나눠도 소수인지 판별이 가능하다. 물론, 이 방법을 ..

티스토리툴바