CS - 뫼비우스 함수
Introduction
혹시 궁금해하는 사람을 위해 미리 말해두지만, 이 뫼비우스가 아니다.
이분이다.
이름 자체는 수학 함수의 대부분이 그렇듯이 만든 사람 이름 따온 별거 아닌 것 같지만, 그 효과만큼은 대단하다. 오늘은 뫼비우스 함수, 그리고 그것을 확장한 뫼비우스 반전 공식을 살펴보자.
Before We Begin..
시작하기 전에, 함수들이 어떻게 생겼는지 정도만 알아보고 가자. 뫼비우스 함수는 아래와 같이 생겼다.
\[\mu(n) = \begin{cases}
1 & \text{if } n = 1 \\
(-1)^k & \text{if } n \text{ is the product of } k \text{ distinct primes} \\
0 & \text{if } n \text{ is divisible by a square } > 1
\end{cases}\]
뫼비우스 반전 공식은 아래와 같다.
\[f(n) = \sum_{d|n} \mu(d)g(\frac{n}{d}) \text{ for every integer }n \geq 1\]
이제부터 각 함수의 자세한 내막을 알아보자.
The Möbius Function
바로 위에 있긴 하지만, 뫼비우스 함수는 아래와 같이 생겼다.
\[\mu(n) = \begin{cases}
1 & \text{if } n = 1 \\
(-1)^k & \text{if } n \text{ is the product of } k \text{ distinct primes} \\
0 & \text{if } n \text{ is divisible by a square } > 1
\end{cases}\]
즉, 1이면 함수는 1, 제곱수로 나누어지면 함수는 0, 아니면 -1의 소수 개수 제곱을 하면 된다.
아래에서 설명하는 것이 조금 더 적절하겠지만, 미리 예열을 해놓자면, 이는 곧 포함과 배제의 기본 배경을 마련한다.
Example
간단한 예시를 생각해보자. 내가 만일 손으로 \(\phi (n)\)를 구하려고 한다면, 식을 어떻게 세워야 할까?
\(n=p_1^{k_1} \cdot p_2^{k_2} \cdot \cdot \cdot p_n ^{k_n} (p_i \in \mathbb{P} \text{, the set of primes})\)이라 생각해보자. 그럼 \(\phi(n)\)를 전개해보면 아래와 같이 될 것이다.
\[\phi(n) = n - \sum_{p | n} \lfloor \frac{n}{p} \rfloor + \sum_{p_i | n} \sum_{p_j | n \text{ & } i < j} \lfloor \frac{n}{p_i p_j} \rfloor\ - \cdot \cdot \cdot (p_k\text{ are all primes)}\]
여기서 눈여겨볼 점은 각 \( \sum\) 앞의 부호이다. 현재 처리하고 있는 '소인수의 개수'를 \(k\)라고 한다면 항 앞의 부호가 \((-1)^k\)가 된다는 것을 알 수 있다. 어디서 많이 본 듯한 식이다.
Compression
Stage 1 : the basics
자 그럼 저 위에 식을 압축할 방법이 있을까? 생각해보자. 만일 \( \sum\)에서 순회하는 값들을 '소인수'가 아니라 '약수'로 바꾸면 어떨까? 식이 아래와 같이 압축된다 :
\[\phi(n) = \sum_{p | n} (-1)^{\omega (n)} \lfloor \frac{n}{p} \rfloor \]
단순 감으로 보면 이게 끝일 것 같을수도 있지만, 우리가 고려 안한 케이스가 있다.
Stage 2 : squares
\(\phi(18) \)를 생각해보자. 18을 소인수분해한다면 2 * 3 * 3이 나올 것이다. 하지만, 우리는 "2개의 소인수로 구성된" 수들을 셀때 9를 세지는 않는다. 왜 그럴까? 이것은 이미 3때 처리되었기 때문이다. 즉, 우리는 같은 소인수가 2번 이상 반복될 경우 사실상 그것이 없는 것처럼 처리해야 한다는 것을 알 수 있다.
Stage 3 : final cleanup
그럼 지금까지 나온 점들을 정리해보자.
\(\phi(n) = \sum_{p | n} k(x) \lfloor \frac{n}{p} \rfloor \)라는 식이 있다고 해보자. 지금까지의 정보를 조합하여 \(k(x)\)를 서술해본다면,
\[k(x) = \begin{cases}
(-1)^k & \text{if } x \text{ is the product of } k \text{ distinct primes} \\
0 & \text{if } x \text{ is divisible by a square } > 1
\end{cases}\]
1은 소인수 0개라고 정리한다면, 저 식은 사실상 \( \mu(n)\)의 식이 된다.
The Mobius Inversion Formula
자, 그럼 위에서 유도한 사실을 공식으로 정리하면 무엇이 될까? 첫 함수의 \((-1)^{\omega (n)}\)를 \(\mu(n)\)으로 치환한다면 아래와 같은 식이 된다.
\[\phi(n) = \sum_{p | n} \mu (n) \lfloor \frac{n}{p} \rfloor \]
축하한다, 이걸 마지막으로 여러분은 뫼비우스 반전 공식, Mobius Inversion Formula를 유도해낸 것이다.
여기서 포인트는 이것이 일반화가 가능하다는 것이다. 서로 간의 합으로 표현되는(\(f(x) = \sum_{d | x} g(d)\)) 함수들은 이 inversion formula를 통하여 역변환이 가능하다(\(g(x) = \sum_{d | x} \mu(d) f(\frac{x}{d})\)).
Example Problem
다른 예시를 살펴보자. 백준 문제이다.
스타트링크 (Startlink)
무언가 익숙해 보인다. 대충 문제의 조건을 식으로 표현하면,
\[\phi(n) = n - \sum_{p}^{p < \sqrt{n}} \lfloor \frac{n}{p^2} \rfloor + \sum_{p_i}^{p_i < \sqrt{n}} \sum_{p_j, i < j}^{p_j < \sqrt{n}} \lfloor \frac{n}{p_i^2 p_j^2} \rfloor\ - \cdot \cdot \cdot \text{(p_k are all primes)}\]
이제는 확실하다. 압축하면,
\[\phi(n) = \sum_{p}^{p < \sqrt{n}} \mu (n) \lfloor \frac{n}{p^2} \rfloor \]
가 된다. 풀이 끝이다. 정답 코드가 궁금하다면 여기에 첨부하였다.
Conclusion
오늘은 정보과학에서 함수의 역함수 계산, 그리고 포함과 배제 구현에 도움이 많이 되는 뫼비우스 함수와 반전 공식에 대하여 알아보았다.
