정수론 기본기 잡기

이 글의 모든 내용은 rkm0959님의 PS를 위한 정수론 가이드를 가져온 것임을 밝힙니다. 정수론 공부가 목적이시라면 위 블로그를 찾아주세요

나눗셈 검산식

정수 $a, b\ (b\neq0)$가 존재할 때, $a=bq + r\ (0 \le r <|b|)$를 만족하는 정수 $q, r$은 유일하다.

몫(Quotient)라는 의미로 $q$라고 쓰고, 나머지(Remainder)라는 의미로 $r$이라고 씁니다. 즉 $a = bq + r$은 초등학교때 배웠던 $a$를 $b$로 나누었을 때 나눗셈 검산식과 같습니다.
$a, b$가 음수여도 마찬가지로 위 조건을 따르는 $q, r$은 유일합니다. 예를 들어, $a, b = -3, 2$라면 $-3 = 2 \times (-2) + 1$이 됩니다. $q, r = -2, 1$이 됩니다.

C/C++에서의 음수 나눗셈

그러나 C/C++에서 음수 나눗셈($a, b$의 부호가 서로 다른 경우)은 조금 다릅니다. C++에서 음수 나눗셈은 음수를 양수로 바꾸고 그냥 나눈 뒤에 몫을 음수로 바꿔줍니다. 따라서 경우에 따라서는 위의 정의와는 다르게 나머지가 음수가 될 수 있습니다. 하지만 이렇게 나누더라도 $q, r$은 유일합니다.
$a, b = -3, 2$라면 $3, 2$로 바꿔서 나눈 뒤 몫에 음수를 취하면 몫은 $-1$이 됩니다. 따라서 자연스럽게 나머지는 $-3 = 2 \times (-1) + r$따라서 $r = -1$이 됩니다.

여담으로 파이썬은 경우는 음수 나눗셈에 대한 동작이 C/C++과 다릅니다.

$a=bq + r\ (0 \le r <|b|)$에서 $r = 0$이라면 $a$와 $b$는 배수, 약수 관계에 있고, 이 때 $b\mid a$라고 쓴다.

$b \mid a$는 $b$가 $a$를 나누어 떨어지게 한다라는 의미입니다. $b \nmid a$는 그 반대의 의미입니다.

$a\pmod{n}$은 $a$를 $n$으로 나눈 나머지를 의미한다.
$a\pmod{n} = b\pmod{n}$일때 이를 $a\equiv b\pmod{n}$라고 한다. 이는 $n \mid (a - b)$와 같은 의미이다.

증명

$a \pmod{n} = b \pmod{n}$이기 때문에 $a = bq + r$꼴로 나타내면
$a = nq_a + r_a, b = nq_b + r_b$로 나타낼 수 있습니다. $a-b$도 같은 꼴로
$a - b = n(q_a - q_b) + r_a - r_b$로 나타낼 수 있는데 $r_a = r_b$이므로 소거할 수 있습니다.
따라서 $a- b = n(q_a - q_b)$이므로 $n \mid (a - b)$입니다.

소수의 정의

$2 \le{k}<n\ (2\le{n})$에 대해 $k \nmid n$이라면 $n$은 소수이다.

$\mathcal{O}(\sqrt{n})$ 소수 판별 알고리즘

$n$이 소수임을 판단하기 위해서는 위 정의처럼 $\mathcal{O}(n)$번 나눠볼 필요 없이 $2\le k \le \sqrt{n}$에 대해 $\mathcal{O}(\sqrt{n})$번만 나눠봐도 됩니다.

증명

$n$이 소수가 아니라면 $n = a \times b$로 나타낼 수 있고, 최소 둘 중 하나는 $\sqrt{n}$보다는 작기 때문에 $2\le k \le \sqrt{n}$에 대해 나눠보면 반드시 나누어 떨어집니다. 만약 둘 다 $\sqrt{n}$보다 크다면 $a \times b$는 $n$보다 커져서 모순이기 때문입니다.

에라토스테네스의 체 활용법

에라토스테네스의 체 알고리즘의 시간 복잡도는 $\mathcal{O}(n\log{\log{n}})$입니다. 같은 알고리즘을 활용하여 여러가지를 전처리 할 수 있습니다.

$k$가 갖는 가장 작은 소인수

에라토스테네스의 체는 작은 소인수 $i$부터 확인하므로 아직 지워지지 않은 숫자 $j$를 만난다면 지금 $i$가 $j$의 가장 작은 소인수가 된다.

$k$가 갖는 서로 다른 소인수

마찬가지로 소인수의 개수를 셀 수 있다.

$\mathcal{O}(\log{n})$ 소인수 분해

naive한 소인수 분해는 $\mathcal{O}(\sqrt{n})$입니다. $k \mid n$이라면 $(n / k) \mid n$이기 때문입니다.
$n$이하의 정수 $k$가 갖는 가장 작은 소인수를 전처리하면 $n$이 $1$이 될 때 까지 계속해서 나눌 수 있습니다. 소인수는 $2$이상이므로 $n$은 최소 절반씩 줄어듭니다. 따라서 $\mathcal{O}(\log{n})$

임의의 구간 에라토스테네스의 체

임의의 구간 $[A + 1, A + n]$구간에 대해서도 빠르게 에라토스테네스의 체를 적용할 수 있습니다.
구간 $i = [2, \sqrt{A + n}]$에 대해서만 적용해도 됩니다.

1. $j$를 $[2, \sqrt{A + n}]$의 배수라고 하면, $j$를 $[A + 1, A + n]$에서 다 지우면 소수만 남게 됩니다.

$\mathcal{O}(\sqrt{n})$ 소수 판별 알고리즘에서 증명했듯 $A + n$이 소수인지 판별하려면 $\sqrt{A + n}$까지만 나눠보면 되기 때문입니다.

2. 각 $j$에 대해 지워지는 $j$의 배수의 개수는 $\mathcal{O}(\displaystyle\frac{n}{k})$

$[A + 1 , A +n]$구간의 길이는 $n$이므로 이 구간에서 반복하는 횟수는 $\mathcal{O}(\displaystyle\frac{n}{j})$
Harmonic Sequence 성질에 의해 $\displaystyle\sum_{j=1}^{n}\frac{1}{j}=\mathcal{O}(\log{n})$이므로
$\mathcal{O}(\displaystyle\frac{n}{j})=\mathcal{O}(n \times \displaystyle\frac{1}{j}) = \mathcal{O}(n \log{n})$
$\mathcal{O}(\sqrt{A + n} + n\log{n})$