Notation

앞으로 PS에서 쓰이는 정수론 관련 글을 쓸 예정인데, 그에 앞서 몇 가지 기호나 앞으로의 글들을 이해하는데 필요한 조금의 배경지식을 미리 정리하고 가려고 한다.

기호

[] 표기를 두 가지로 쓸 것이다.

$[P]$: 대괄호 안에 명제가 들어 있다면, 참일 때 1이고 거짓일 때 0을 의미하는 기호이다. Iverson bracket이라 부른다.

$[x]$: 대괄호 안에 실수가 들어 있다면, 가우스 함수로 x 이하의 최대 정수를 의미한다. Floor function이라고도 부른다.

가우스 함수의 두 가지 중요한 성질은 다음과 같다.

$n$ 이하의 $d$의 배수의 개수는 $[\frac{n}{d}]$개 이다.

실수 $x$와 자연수 $n$에 대해, $[\frac{x}{n}]=[\frac{[x]}{n}]$이다. 특히, 자연수 $n$, $m$에 대해 $[\frac{\frac{x}{n}}{m}]=[\frac{x}{nm}]$이다.

$\displaystyle \sum_{d \vert n}$: 자연수 $n$의 양의 약수 $d$에 대한 합을 의미한다.

함수

정수론에서 유용하게 쓰이는 함수가 여럿 있다. 한번 살펴보자.

편의상 $n$을 소인수분해하여 $n=\displaystyle \prod_{i=1}^k {p_i}^{e_i}$로 나타내었다고 하자.

$\tau(n)$: $n$의 양의 약수의 개수를 나타내며, $\tau(n) = \displaystyle \sum_{d \vert n} 1 = \displaystyle \prod_{i=1}^k (e_i + 1)$ 이 성립한다.

$\sigma(n)$: $n$의 양의 약수의 합을 나타내며, $\sigma(n) = \displaystyle \sum_{d \vert n} d = \displaystyle \prod_{i=1}^k (\frac{ {p_i}^{e_i + 1}-1 }{ p_i - 1 })$ 이 성립한다.

$\phi(n)$: $n$ 이하의 자연수 중 $n$과 서로소인 수의 개수를 나타내며, $\phi(n) = n\displaystyle \prod_{i=1}^k (1-\frac{1}{p_i})$ 이 성립한다.

$\mu(n)$: $e_i$ 중 $2$ 이상인 것이 있다면 $0$, 그렇지 않다면 $(-1)^k$을 나타내는 함수이다.

이 외에는 편의상 정의하는 함수들이다.

$I_k(n) = n^k$: $k$제곱을 나타내는 함수이다.

$1(n) = 1$: 상수함수이다.

$\epsilon(n) = [n=1]$: $n$이 $1$일 때 $1$, 아닐 때 $0$을 나타내는 함수이다.

위에서 언급한 함수는 모두 multiplicative function(곱셈적 함수)으로, 서로소인 두 자연수 $n$, $m$에 대해 $f(n)f(m) = f(nm)$이 성립한다. 따라서 소수 p에 대해 $f(p^k)$ 에 대한 공식만 있으면 모든 자연수에 대한 함숫값을 알 수 있다.

multiplicative function $f(n), g(n)$에 대해, 다음 함수 역시 multiplicative function이다. \[h(n) = f(n)g(n)\] \[h(n) = \displaystyle \sum_{d \vert n} f(n)g({n \over d})\]

특히 $h(n) = \displaystyle \sum_{d \vert n} f(n)$ 역시 multiplicative function이다.

앞으로 다룰 글은 주로 정수론 함수들로 표현된 합을 빠르게 계산하는 방법에 대한 내용이다. \[\displaystyle \sum_{i=1}^n \tau(i)\] \[\displaystyle \sum_{i=1}^n \displaystyle \sum_{j=1}^n gcd(i, j)\]

같은 식을 계산하게 될 것이다.