기초 수학 모음

조화수

$$\sum_{i=1}^{n}{\frac{n}{i}} < n\ln n$$ 따라서 시간복잡도도 서로 같다고 볼 수 있음.

페르마 소정리

$$a^p \equiv a \pmod p $$ $$a^{p-1}\equiv 1 \pmod p$$ $$a^{p-2}\equiv a^{-1} \pmod p$$

증명

• Lemma

$p$의 reduced residue system $\set{1, 2,3,\dots, p - 1}$에 $a$를 곱한 $\set{a, 2a,\dots, (p-1)a}$의 나머지 집합 또한 이 집합과 같다.

• 본 증명

$\set{1, 2,3,\dots, p - 1}$ = $\set{a \pmod p, 2a \pmod p,\dots, (p-1)a \pmod p}$

이때 양 집합의 원소를 서로 곱하면

$$(p-1)! \equiv a^{p-1}(p-1)! \pmod p$$ 따라서

$$1 \equiv a^{p-1} \pmod p$$

조합

$\binom{n}{k} \pmod p$를 구하는 방법.

1. 파스칼 DP

$$\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k}$$

이를 이용하면 $O(n)^2$에 가능

2. 페르마 소정리

$n! \pmod p$는 $O(n)$에 구할수 있고, $n!^{-1} \pmod p$도 $n!$을 알고 있으면 분할 정복을 통한 제곱 수 구하기를 통해 $\lg p$에 페르마 소정리를 통해서 구할 수 있다.

이후 $i!^{-1}\pmod p$는 $(i-1)! \equiv i!\times i \pmod p$를 통해 귀납적으로 구할 수 있다.

따라서 구하고자 하는 식은 다음과 같이 구할 수 있다: $$\binom{n}{k} = n! (n-k)!^{-1}k!^{-1}\pmod p$$

전체적인 시간복잡도는 $O(n + \lg p)$