7. Mobius function과 그 활용

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

이 단원의 내용은 특정 값을 계산하는 알고리즘과 그 template code가 명확하게 있지 않다.

즉, 이 단원에 관한 문제 풀이는 template을 복사/붙여넣기하는 방식으로 풀기 어렵다. 

대신, 문제풀이를 위해서 알아야 하는 이론의 양은 상대적으로 적다. 적은 이론 + 많은 식 정리로 풀리는 문제가 대부분이다.

하지만 "이 단원의 내용이 포함-배제의 원리와 같다"는 점을 제대로 이해하면, 문제풀이가 더 쉬워질 수도 있다. 

그러나 이 점을 제대로 이해하지 않아도 문제는 풀 수 있으니, 이 부분은 부록으로 옮긴다. 그래도 부록을 한 번 읽는 것을 추천.

mobius function $\mu(n)$은 각 자연수에 대하여 다음과 같이 정의된다.

• $n = 1$인 경우, $\mu(n) = 1$이다.
• 만약 소수 $p$가 존재하여 $p^2|n$이라면, $\mu(n) = 0$.
• $n = p_1p_2 \cdots p_k$라면 (단, $p_i$는 서로 다른 소수) $\mu(n) = (-1)^k$

이때, mobius function은 다음과 같은 성질을 갖는다.

• $\mu$는 multiplicative. 즉, $m, n$이 서로소인 자연수라면 $\mu(mn) = \mu(m)\mu(n)$. 이는 정의에서 바로 증명할 수 있다.
• 각 자연수 $n$에 대하여 $\sum_{d|n} \mu(d)$의 값은 $n=1$인 경우 $1$이고, $n \ge 2$인 경우에는 $0$이다. 증명은 뒤로 미룬다.
• mobius inversion. $f(n) = \sum_{d|n} g(d)$라면, $g(n) = \sum_{d|n} \mu(n/d) f(d)$가 성립한다.
• 예시. 오일러 정리 단원에서 $n = \sum_{d|n} \phi(d)$라고 했다. 그러니 $\phi(n) = \sum_{d|n}  d \mu(n/d)$다.
• $\sum_{d|n} d \mu(n/d)$라는 식은, $n$의 소인수분해를 생각한 후 계산하면 $n(1-1/p_1)(1-1/p_2) \cdots (1-1/p_k)$와 같다.
• $\mu(1), \mu(2), \cdots , \mu(n)$을 전부 계산하는 것은 에라토스테네스의 체로 할 수 있다. github 코드 참조.

사실 이게 CP/PS에서 쓰는 성질 전부다. 이걸 잘 조합해서 문제를 풀어내는 것이 어려운 것이다. 

• mobius function이란 말을 들으면 mobius inversion을 생각하는 경우를 봤다. 하지만 실제로 mobius inversion 식 자체는 많이 쓰이지 않는다.

• 사실 mobius function을 이용한 문제풀이의 핵심은 $\sum_{d|n} \mu(d)$가 $n=1$일 때만 $1$, 아니면 $0$이라는 점이다. 

• 계속 강조하지만, mobius inversion은 포함-배제와 같다. 부록 참고.

이제부터 시범을 보인다. 식 조작의 편의를 위하여, Iverson bracket을 도입한다.

• 명제 $P$에 대하여, $[P]$의 값은 $P$가 참이면 $1$, 아니면 $0$이다. 

• 이제 $\sum_{d|n} \mu(d) = [n=1]$이라고 쓸 수 있다. 이 식이 문제풀이의 핵심이다.

BOJ 16409 : Coprime Integers

문제에서 요구하는 값은 $$\sum_{x=a}^b \sum_{y=c}^d [\text{gcd}(x, y)=1]$$이다. $\sum_{d|n} \mu(d) = [n=1]$을 사용하여 Iverson bracket을 없애면, $$ \sum_{x=a}^b \sum_{y=c}^d \sum_{g|x, g|y} \mu(g) $$를 얻는다. 이제 식을 바라보는 관점을 바꾸자. $x, y$에 대해서 iterate 한 다음 $g|x, g|y$를 만족하는 $g$를 보는 것이 아니라, $g$를 고정하고 $g$의 배수가 되는 $x, y$에 대해서 iterate 하자. 이렇게 식을 변형하는 방식을 보통 "double counting"이라고 부른다. 그러면 우리의 식이 $$ \sum_{g=1}^{\text{min}(b, d)} \mu(g) \cdot ([a, b] \text{ 에 존재하는 } g \text{의 배수 개수}) \cdot ([c, d] \text{ 에 존재하는 } g \text{의 배수 개수}) $$가 된다. 물론, $[a, b]$에 존재하는 $g$의 배수 개수는 $\lfloor b/g \rfloor - \lfloor (a-1)/g\rfloor$이고, $[c, d]$에 대해서도 마찬가지다. 즉, 답은 $$ \sum_{g=1}^{\min(b,d)} \mu(g) \cdot (\lfloor b/g \rfloor - \lfloor (a-1)/g \rfloor) \cdot (\lfloor d/g \rfloor - \lfloor (c-1)/g \rfloor)$$가 된다. 이제 $\mu$를 전처리하면 답을 쉽게 계산할 수 있다.

여기서도 볼 수 있지만, 약수에 대해 iterate 하는 것보다 배수에 대해 iterate 하는 것이 더 쉽다는 점을 많이 이용한다. (아래에 예시를 더 넣어두겠다)

시범을 한 번 더 보이겠다. 이번에는 $$\sum_{x=1}^n \sum_{y=1}^n \text{gcd}(x, y)$$를 구해보자. 이를 위해서 $\text{gcd}(x, y) = d$인 $(x, y)$의 개수를 각 $d$에 대해서 구해보자. 이 값을 구하려면, $$ \sum_{x=1}^n \sum_{y=1}^n [\text{gcd}(x, y)=d]$$를 구하면 된다. 그러니, 기존 식의 값은 $$ \sum_{d=1}^n d \cdot \sum_{x=1}^n \sum_{y=1}^n [\text{gcd}(x, y)=d]$$와 같다. $\text{gcd}(x, y)=d$려면, $x, y$ 역시 $d$의 배수여야 하니 $x=da$, $y=db$라 쓸 수 있고, 이때 $1 \le a, b \le \lfloor n/d \rfloor$와 $\text{gcd}(a, b)=1$이다. 즉, 식은 $$ \sum_{d=1}^n d \cdot \sum_{a=1}^{\lfloor n/d \rfloor} \sum_{b=1}^{\lfloor n/d \rfloor} [\text{gcd}(a, b)=1]$$과 같다. 이제 바로 앞의 문제의 결과를 적용하면 $$ \sum_{d=1}^n \sum_{g=1}^{\lfloor n/d \rfloor} d \mu(g) \cdot \lfloor \frac{n}{gd} \rfloor^2$$을 얻는다. 여기서 자연수 $n, a, b$에 대하여 $\lfloor n/(ab) \rfloor = \lfloor \lfloor n/a \rfloor / b \rfloor$임을 이용하였다.

• Finish 1. $\mu$를 전처리하자. 위 합을 for 문으로 계산하면, 시간복잡도는 $\sum_{d=1}^n \lfloor n/d \rfloor = \mathcal{O}(n \log n)$ (by Harmonic Sequence)

• Finish 2. $gd$라는 값이 심상치 않다. $gd = T$라고 치환을 한 다음, $T$를 기준으로 계산을 해보자. 그러면 $$ \sum_{T=1}^n \lfloor n/T \rfloor^2 \cdot \sum_{d|T} (d \cdot \mu(T/d))$$라는 식을 얻는다. 그런데 $\phi(T) = \sum_{d|T} (d \cdot \mu(T/d))$임을 앞에서 언급했다. 그러니 식은 $ \sum_{T=1}^n \lfloor n/T \rfloor^2 \phi(T)$와 같다. 

위 문제의 mobius function을 사용하지 않는 풀이를 소개한다. $cnt[d]$를 $\text{gcd}(x, y) = d$인 $x, y$의 개수라고 하자. 사실 우리는 $\text{gcd}(x, y) = d$인 $x, y$의 개수는 세기 어려워해도, $\text{gcd}(x, y)$가 $d$의 배수인 것은 쉽게 셀 수 있다. $x, y$가 각각 $d$의 배수이면 충분하므로, 정확히 $\lfloor n/d \rfloor^2$개 존재할 것이다. 이는 사실 $$ cnt[d] + cnt[2d] + \cdots + cnt[d \cdot \lfloor n/d \rfloor]  = \lfloor n/d \rfloor^2$$이 성립한다는 것이다. 이를 통해서, $cnt$ 배열을 모두 구할 수 있다. 다음과 같은 코드를 생각하면 이해가 될 것이다.

for(i=1 ; i<=n ; i++) cnt[i] = (n/i) * (n/i);
for(i=n ; i>=1 ; i--)
    for(j=2*i ; j<=n ; j+=i) cnt[i]-=cnt[j];

더욱 놀라운 점은, Harmonic Sequence의 성질 때문에 이 코드 역시 시간복잡도가 $\mathcal{O}(n \log n)$이란 것이다.

• 이 풀이를 보면서, "배수에 대해 iterate 하는 것이 효율적이다"라는 말의 의미를 느낄 수 있다.

• 또한, 이 풀이가 굉장히 포함-배제의 원리 느낌이 난다는 것을 느낄 수 있을 것이다. 

물론, 실제로 문제를 해결하려면 $\sum d \cdot cnt[d]$를 계산하면 끝이다. 

이제부터 "배수에 대해 iterate 하는 것"과 double counting을 사용한 간단하지만 중요한 예제를 몇 개 제시한다.

• $\tau(n)$을 $n$의 약수의 개수라고 정의한다. $\sum_{i=1}^n \tau(i)$를 어떻게 계산할까?  

• $\sigma(n)$을 $n$의 약수의 합이라고 정의한다. $\sum_{i=1}^n \sigma(i)$를 어떻게 계산할까?

$\sum_{i=1}^n \tau(i)$는 결국 $g|i$, $1 \le i \le n$을 만족하는 순서쌍 $(g, i)$의 개수이다. 순서쌍의 개수를 $i$ 기준으로 세면, 각 $i$에 대해 조건을 만족하는 $g$가 $\tau(i)$개 있기 때문이다. 순서쌍의 개수를 $g$ 기준으로 세면, 조건을 만족하는 $i$가 $\lfloor n/g \rfloor$개 있음을 알 수 있다. 그러니 순서쌍의 개수는 $\sum_{g=1}^n \lfloor n/g \rfloor$이다. 그러므로, $$ \sum_{i=1}^n \tau(i) = \sum_{i=1}^n \lfloor n/i \rfloor $$이다. 이는 결국 "각 정수에 대해 약수의 개수를 센다"에서 "각 정수에 대해 배수의 개수를 센다"로 문제를 바꿔 생각해서 얻은 결과이다. 위 식의 우변은 자명하게 $\mathcal{O}(n)$에 계산할 수 있다. 또한, $\lfloor n/i \rfloor$로 가능한 값의 개수가 $\mathcal{O}(\sqrt{n})$개이며, 그 값을 갖게 하는 $i$의 범위 역시 계산할 수 있음은 이미 1단원에서 언급하였다. 이를 사용하면, 우변의 값을 $\mathcal{O}(\sqrt{n})$에 계산할 수 있다. 이러한 방식은 후에 multiplicative function을 다룰 때 더 나온다.

$\sum_{i=1}^n \sigma(i)$ 역시, 같은 방법으로 생각하면 $\sum_{g=1}^n g \lfloor n/g \rfloor$임을 얻는다. 이는 $\mathcal{O}(n)$에 자명하게 계산할 수 있다. 특정 구간에 속한 정수의 합, 즉 $\sum_{i=a}^b i$를 쉽게 계산할 수 있으므로, $\lfloor n/g \rfloor$로 가능한 값이 $\mathcal{O}(\sqrt{n})$개임을 이용하여 우변의 값을 $\mathcal{O}(\sqrt{n})$에 계산할 수 있다. github 코드 참고.