1. 기본기 잡기

관련 코드는 github에서 찾아볼 수 있다.

여기서는 잘 알려진 사실들부터 시작해서, 나중에 중요해질 수학적 사실들을 다룬다.

사실 1단원과 2단원 앞 유클리드 알고리즘만 알아도 퍼플/오렌지에 영향은 없다.

잘 알려진 사실들은, 매우 간단하게만 설명하고 스킵하자. 이미 좋은 자료/블로그가 많으니, 이를 참고하는 것 추천.

다음 사실은 유명하다 : 정수 $a, b$가 있고 $b \neq 0$일 때, $a = bq + r$이고 $0 \le r < |b|$인 정수 $q, r$이 유일하게 존재한다.

이때, $r$을 "$a$를 $b$로 나눈 나머지"라고 정의한다. 만약 $r = 0$인 경우, $a, b$는 서로 약수/배수 관계에 있다고 하며, $b|a$라 쓴다.

이를 통해서 공약수/공배수 개념을 정의할 수 있으며, 나아가 최대공약수/최소공배수의 개념을 정의할 수 있다.

자연수 $n \ge 2$가 각 $2 \le k < n$에 대하여 $k \nmid n$을 만족하면, $n$을 소수라고 부른다. 소수가 아니면 (1 제외) 합성수라고 부른다. 

이를 통해서 소인수분해라는 개념을 정의할 수 있으며, 이는 유일하다는 것이 잘 알려져 있다.

소인수분해를 통해서, 자연수의 약수의 개수와 약수들의 합 등을 계산할 수 있음은 교육과정에도 있는 내용이다.

만약 두 정수 $a, b$가 $n$으로 나눈 나머지가 같다면, $a \equiv b \pmod{n}$이라고 쓴다. 이는 $n|(a-b)$와 같은 뜻이다.

또한, $a$를 $n$으로 나눈 나머지를 $a \pmod{n}$이라고 쓰기도 한다. 다음은 간단 Exercise.

• 정수 $a, b, n$이 $a \equiv b \pmod{n}$이고, $r$이 정수인 경우, 다음이 모두 성립함을 보여라.
• $a + r \equiv b+ r \pmod{n}$, $a - r \equiv b - r \pmod{n}$, $ar \equiv br \pmod{n}$.

즉, mod 연산을 취하는 과정에서도 평소처럼 사칙연산을 할 수 있다. 

나눗셈이 문제인데, 다음 단원에서 modular inverse가 나오면 나눗셈도 modular inverse를 양변에 곱하는 방식으로 할 수 있다.

이 시점에서, 알고리즘 문제를 몇 개 생각해볼 수 있다. 모두 이미 자료가 많으므로, 빠르고 간단하게 한다.

• 자연수가 소수임을 어떻게 판별할 것인가?
• 자연수의 약수의 개수를 어떻게 셀 것인가? 약수를 모두 찾으라고 한다면 어떻게 할 것인가?
• 자연수의 소인수분해를 어떻게 구할 것인가?
• 1부터 $n$까지의 소수를 어떻게 셀 것인가/찾을 것인가?

첫 세 문제에 대해서는, $\mathcal{O}(\sqrt{n})$ 알고리즘이 잘 알려져 있다. 핵심 아이디어는,

• 자연수 $n$이 $2$ 이상 $\sqrt{n}$ 이하 모든 자연수에 의해 나누어떨어지지 않는다면, $n$은 소수다.
• 이유: 소수가 아니라면 $n = ab$이며 $1  < a , b < n$인 자연수 $a, b$ 존재. 둘 다 $\sqrt{n}$보다 크다면 $ab > n$.

이 핵심 아이디어로 세 문제를 해결해보자.

• 소수 판별: $2$ 이상 $\sqrt{n}$ 이하 모든 자연수에 대해 나누어떨어짐을 판별하면 끝.
• 약수 세기/찾기: $a$가 $n$의 약수면 $n/a$ 역시 $n$의 약수. 둘 중 하나는 $\sqrt{n}$ 이하고 하나는 $\sqrt{n}$ 이상이니, $\sqrt{n}$ 이하 약수만 찾으면 모든 약수를 알 수 있다.
• 소인수분해: $2$ 이상 $\sqrt{n}$ 이하 모든 자연수를 순서대로 보자. 현재 보고 있는 자연수 $i$가 $n$의 약수라면, $n$이 $i$의 배수가 아닐 때까지 $n$에서 $i$를 나누어준다. 나누어주는 횟수를 저장하는 것은 당연. 만약 iteration이 끝났을 때, $n$이 $1$이면 그대로 끝. 아니면 남은 $n$ 역시 소수이며, 기존 $n$의 소인수가 된다. 

마지막 문제는 "에라토스테네스의 체"로 잘 알려져 있는 결과다.

• 에라토스테네스의 체: 2부터 $n$까지 순서대로 보면서, 합성수인 것을 지워내자. 만약 지금 보는 값 $p$가 지워지지 않았다면, $p$는 소수다. 
• 이제 $p$의 배수를 ($p$는 빼고) 전부 지워내자. 이걸 반복하면 남는 것은 전부 소수. 예시를 인터넷에서 찾아보면서 이해해보자. 

에라토스테네스의 체는 활용 방법이 굉장히 많다. 다음을 할 수 있는 방법을 생각해보자. 해답은 github에 있다.

• 각 $2$부터 $n$까지의 자연수에 대하여, "그 자연수가 갖는 가장 작은 소인수"를 계산하는 법
• 각 $2$부터 $n$까지의 자연수에 대하여, "그 자연수가 갖는 서로 다른 소인수 개수"를 계산하는 법
• 오일러 파이 함수. $n$의 소인수분해가 $p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$일 때, $\phi(n) = n \cdot \frac{p_1 - 1}{p_1} \cdots \frac{p_k-1}{p_k}$라 정의하자. 이 값을 모두 계산하는 법.
• 조금 더 난이도가 있지만, "약수의 개수"와 "약수의 배수" 역시 전처리 할 수 있다.

여기서 강력한 결과를 하나 얻을 수 있다.

• 각 $2$부터 $n$까지의 자연수에 대하여, "그 자연수가 갖는 가장 작은 소인수"를 미리 전처리했다고 가정하자.
• 이제 $2 \le m \le n$인 자연수 $m$의 소인수분해를 원한다고 가정하자. 
• $m$에서 시작해서, "가장 작은 소인수"를 나누어주는 과정을 반복하자. 한 번에 값이 반 이상 줄어드니, 로그 시간에 소인수분해 끝.

에라토스테네스의 체를 사용하면 $1, 2, \cdots , n$ 각각이 소수인지 전부 빠르게 판별할 수 있다.

하지만 꼭 $1$부터 시작할 필요는 없다. $A+1, A+2, \cdots , A+n$ 각각이 소수인지 빠르게 판별할 수는 없을까?

• $2$부터 $\sqrt{A+n}$까지의 수를 순서대로 보자. 현재 보고 있는 수를 $k$라고 하자.
• $A+1, A+2, \cdots , A+n$에 속한 $k$의 배수 중 $k$가 아닌 것을 전부 제거하자. 남는 것은 전부 소수이다.
• 시간복잡도는 어떻게 될까? 각 $k$에 대하여 제거되는 수의 개수는 $\mathcal{O}(n/k)$개이다.
• 이를 $k$를 $2$부터 $\sqrt{A+n}$까지 돌면서 더하면, 아래에서 다룰 Harmonic Sequence에 대한 성질에 의해 총 $\mathcal{O}(n \log n)$이 된다.
• 그러니 $k$에 대하여 for문을 돌리기 위해 필요한 시간 $\mathcal{O}(\sqrt{A+n})$을 더하면, $\mathcal{O}(\sqrt{A} + n \log n)$이라는 결과를 얻는다.
• 에라토스테네스의 체의 다양한 활용 방법을 이 방식에서도 그대로 적용할 수 있다.

참고할 점은, 위의 에라토스테네스의 체가 하는 일을 $\mathcal{O}(n)$에 하는 방법이 존재한다는 것이다.

• Linear Sieve라고 하는 테크닉이다. 이를 위해서는 ahgus89님의 이 자료나, 원본이라고 할 수 있는 이 글을 보자.
• 이후에 다룰 multiplicative function에 대한 글을 읽고 다시 위의 자료를 읽는 것이 이해하기 편할 수 있다.
• 이 가이드에서 굳이 Linear Sieve를 설명하지 않는 이유는, 필자도 Linear Sieve가 필요할 정도로 시간제한이 빡빡한 문제를 본 적이 없기 때문이다.
• 이 외에도, 에라토스테네스의 체는 다양한 최적화 방법이 있다. 개인적으로는 필요한 문제를 본 적이 없었다. 필요하면 나쁜 문제라는 것이 내 생각.
• 당연하지만, 이러한 체 최적화 방법을 알아둬서/팀노트에 넣어서 나쁠 것은 없다. 나중에 관심이 생기면 보는 것으로.

이제 여러 수학적 사실들을 빠르게 다룬다. 중요해지는 때가 온다.

• [매우 중요] 자연수 $n$에 대하여, $\lfloor n/1 \rfloor, \lfloor n/2 \rfloor, \cdots, \lfloor n/n \rfloor$ 중 서로 다른 것은 $\mathcal{O}(\sqrt{n})$개이며, 효율적인 iteration도 가능. github 참조.
• 이유가 꽤 아름다우니 설명한다. $\lfloor n/1 \rfloor, \cdots , \lfloor n / \lfloor \sqrt{n} \rfloor \rfloor$까지 서로 다른 것은 $\mathcal{O}(\sqrt{n})$개. (항 개수가 애초에 $\mathcal{O}(\sqrt{n})$개이므로)
• $\lfloor n / \lfloor \sqrt{n} \rfloor \rfloor, \cdots ,\lfloor n/n \rfloor$까지 서로 다른 것도 $\mathcal{O}(\sqrt{n})$개. (값들이 전부 $\mathcal{O}(\sqrt{n})$ 이하이므로)
• 위 github 코드의 iteration 방법의 원리가 궁금할 수 있을 것이다. 이것의 대한 설명은 ahgus89님의 이 글 참고.
• [매우 중요] Harmonic Sequence. 자연수 $n$에 대하여, $1/1 + 1/2 + 1/3 + \cdots + 1/n = \mathcal{O}(\log n)$.
• 7단원에서 언급하겠지만, 이를 통해서 $1$부터 $n$까지 약수의 개수 합이 $\mathcal{O}(n \log n)$임을 얻는다.
• 그러므로, 만약 필요하다면, $1$부터 $n$이 갖는 약수들을 std::vector 등 자료구조에 $\mathcal{O}(n \log n)$ 시간에 넣을 수 있다.
• 더욱 자세한 내용을 알고 싶다면, 7단원에서 "약수를 iterate 하는 것보다 배수를 iterate 하는 것이 쉽다"는 부분을 읽자.
• Merten's 2nd Theorem. 자연수 $n$에 대하여, $n$ 이하 소수들의 역수의 합은 $\mathcal{O}(\log \log n)$.
• Merten's 2nd Theorem으로, 에라토스테네스의 체의 시간복잡도를 파악할 수 있을 것이다. $\mathcal{O}( n \log \log n)$.
• 후반부의 내용에서, 은근슬쩍 자연수 $a, b, c$에 대하여 $\lfloor \lfloor a/b \rfloor / c \rfloor = \lfloor a/(bc) \rfloor$라는 식을 꽤 사용한다.

마지막으로, 모듈로 연산에 대해 잠깐 언급한다. 이 연산은 덧셈, 뺄셈에 비해서는 물론, 곱셈에 비해서도 느린 연산이다.

그러니, 모듈로 연산을 마구잡이로 사용하면 비효율적인 코드가 나오게 될 것이다. 이를 최적화하는 방법을 간단히 소개한다.

모듈로 연산 횟수를 줄이는 법

• 가능하면 진짜 나머지를 취하지 말고, 모듈러스를 더하고 빼는 것으로 대체한다.
• 예를 들어, $0 \le a < M$, $0 \le b < M$에 대해, $a+b \pmod{M}$을 계산하기 위해서 모듈로 연산을 쓰지 말자는 것이다.
• $a+b$를 계산한 다음, $M$보다 큰 경우 $M$을 빼는 것이 훨씬 효율적이다. 쉽고 확실한 최적화 방법이다.

모듈로 연산 자체를 빠르게 하는 방법

• 모듈로를 가능하면 const로 선언하자. 그러면 상당한 속도 개선을 확인할 수 있다.
• 이러한 고속화의 원리 중 하나는 Barrett Reduction이다. modulo 연산을 곱셈과 시프트 연산으로 대체한다.
• 자세한 내용을 알고 싶다면, 이 위키피디아 글과 이 min_25의 글을 확인하라.
• 어셈블리를 잘 아는 사람이라면 어셈블리를 이용할 수 있는 것으로 안다. 이 부분은 내가 모르니 생략. 이 링크를 보자.
• 관련 내용이 KAIST의 ICPC팀이었던 더불어민규당의 팀노트에도 있다. Fast LL Division/Modulo 부분을 보자.