Möbius 함수의 정의와 활용

약수 관계에서의 포함-배제의 원리

이제 이를 약수-배수 관계에서 생각해보자. 자연수 n이 주어졌을 때 \(S\_n\)을 정의할 수 있고, m이 n의 배수일 때 \(S\_m \subset S\_n\) 이 성립한다고 하자. 다시 말해, 각 집합끼리의 포함관계가 약수-배수 관계에 따라 정해지는 상황이다. 잘 와닿지 않는다면 간단히 \(S\_n\)을 (max 이하의 자연수들 중) \(n^2\)의 배수들의 집합¹이라고 가정하고 읽어보자. 모든 자연수 n에 대해 \(\|\bigcup \_{i=2}^{n}S\_{i}\|\) 를 구하려면 어떻게 해야 할까?

먼저 다음과 같은 성질을 알 수 있다.

• 자연수 \(a\)에 대해 \(S\_a\)를 고려했으면 \(S\_{a^2}, S\_{a^3}\) 등은 고려할 필요가 없다
• \(\bigcup \_{i=2}^{n}S\_{i}\) 은 소수 \(p\_i\)들만을 고려한 \(\bigcup \_{p\_i} S\_{p\_i}\) 와 같다.

그렇다면 포함-배제의 원리에 따라 \(\left\|\bigcup \_{i=2}^{n}S\_{i}\right\|\)는 다음과 같이 구할 수 있다.

1. 소수 \(p\_i\)들에 대해 \(\sum\_i \left\| S\_{p\_i} \right\| \) 를 구해 더한다
2. \(i < j\) 에 대해 \(\sum\_{i뺀다
3. \(i < j < k\) 에 대해 \(\sum\_{i더한다
4. (이하 반복)

고려해야 할 경우의 수가 작으면 \(O(2^n)\) 복잡도를 가지는 알고리즘으로 전체 경우의 수를 구할 수 있다. 그러나 수가 증가할수록 모든 경우를 고려하는 복잡도는 크게 증가한다. 뫼비우스 함수를 이용하면 이와 같은 포함-배제를 비교적 간단히 처리할 수 있다.

여기서는 단순히 집합의 크기만을 고려했지만 \( S = \bigcup \_{i=2}^{n}S\_{i} \)에 대해 소속 원소의 함수값들의 aggregation을 구하는 경우, 즉 \(\sum\_{x \in S} f(x)\) 나 \(\prod\_{x \in S} f(x)\) 를 구하는 상황으로도 어렵지 않게 확장할 수 있다.

프로그래밍 언어로의 구현 (C++)

마지막으로 mu의 계산에 대해 알아보자. 주 원리는 다음과 같다.

• 모든 자연수 s는 \(m \times p\) 형태로 표현할 수 있다. (p는 s의 가장 작은 소인수)
  • 이때 m이 p의 배수이면 s는 제곱수를 인자로 가진다.

그러면 n 이하의 소수 리스트 vector<int> pvec을 이용해 다음과 같이 int mu[n] 배열을 채울 수 있다.

int  mu[n+1];
bool isPrime[n+1];
vector<int> pvec;

fill(isPrime, isPrime+n+1, true);
fill(mu, mu+n+1, -1);

mu[1] = 1;
for(int i=2;i<=n;i++)
{
    if(isPrime[i])
        pvec.push_back(i);

    for(int p : pvec)
    {
        if(i*p > n) break;
        
        isPrime[i*p] = false;
        
        if(i%p == 0)
        {
            mu[i*p] = 0;
            break;
        }
        mu[i*p] = mu[i]*mu[p];
    }
}

연습문제

• [BOJ 1557번] 제곱 ㄴㄴ : 본문에서 예시로 든 상황과 정확히 같다. “K 이하의 제곱 ㄴㄴ수"가 아닌 “K번째 제곱 ㄴㄴ수"임에 유의하자.

• [Codeforces] D. Steps to One (Round #548, Div.2)

  포함배제를 O(2^n)에 진행할 수도 있지만 뫼비우스 함수와 Linearity of Expectation을 이용해 해결하는 풀이가 존재한다. “마지막 (1이 아닌) gcd가 k의 배수였을 때, 길이의 기대값”을 생각해보고 k=6인 상황은 k=2인 경우와 k=3인 경우 양쪽으로 해당될 수 있다는 점을 염두에 두면서 풀어보자.