포함과 배제, 그리고 뫼비우스 함수

INTRO

적당히 꼼수를 써가면서 풀었는데 수학적으로 멋진 풀이를 가진 문제가 있어서 정리해본다.

제곱ㄴㄴ수
이 문제인데 풀 때는 몰랐지만 따로 공부한 후 다시 봤더니 포함과 배제, 더 나아가 뫼비우스 함수까지 개념을 접할 수 있는 아주 좋은 문제다. 이 문제를 풀어가는 과정에서 이 개념들을 접하면 더 이해하기도 쉬울 것 같다.

 

문제 해결

구간 내에서 square-free의 개수를 구하는 문제이다. square-free 수란 소인수 분해를 했을 때 제곱 인수가 없는 수를 뜻한다.

f(n) = 1부터 n까지의 수 중에서 square free 한 수의 개수

 

위와 같이 f(n)을 정의하면 f(max) - f(min - 1) 을 출력하면 된다.
그럼 f(n)과 친해지기 위해 바로 식을 세우기 전에 손으로 직접 f(42)을 구해보자.

 

f(42)를 직접 구해보기

일단 가장 작은 제곱수인 $ 2^{2} = 4 $ 의 배수들(4, 8, 12, 16, 20, 24, 28, 32, 36, 40)은 모두 제거된다. 그 다음 작은 제곱수인 $ 3^{2} = 9 $ 의 배수들(9, 18, 27, 36)도 역시 제거된다. 그 다음 $ 4^{2} = 16 $ 의 배수들(16, 32)가 제거되고, 이어서 25, 36이 제거된다.

 

어떤 수를 제거해야 하는지 알았으니 개수를 세보자.

1. 4의 배수는 $ \lfloor \frac{42}{4} \rfloor = 10 $ 개
2. 9의 배수는 $ \lfloor \frac{42}{9} \rfloor = 4 $ 개
3. 16의 배수는 $ \lfloor \frac{42}{16} \rfloor = 2 $ 개
4. 25의 배수는 $ \lfloor \frac{42}{25} \rfloor = 1 $ 개
5. 36의 배수는 $ \lfloor \frac{42}{36} \rfloor = 1 $ 개

 

그러면 f(42) = 42 - 10 - 4 - 2 - 1 - 1 이면 좋겠지만 16, 32, 36과 같이 중복으로 제거되는 수가 존재하기 때문에 중복을 제거해주는 작업을 추가로 해줘야 한다.

 

중복 처리

중복을 제거하기 전에 아예 계산할 필요조차 없는 수도 있다.

 

어떤 수에 대해서는 더해주고, 어떤 수에 대해서는 빼주고, 어떤 수에 대해서는 무시해야 하니 {+1, -1, 0}을 가지는 뫼비우스 함수 $ \mu(n) $ 을 도입하자.

 

16의 경우는 $ 16 = 4^{2} $ 이기 때문에 16으로 할 수 있는 처리는 4에서 전부 가능하다. 16은 무시하면 된다.

이를 일반화해보자.

 

임의의 수 n에 대해서 n을 소인수분해했을 때 소수 $ p $ 의 지수가 2 이상인 $ p $ 가 존재한다면, $ p $ 에서 처리하면 되기 때문에 계산할 필요가 없다. 이런 n에 대해서 $ \mu(n) = 0 $ 라고 정의하자. 작은 수부터 찾아보면 $ \mu(4) =  \mu(8) = \mu(9) = \mu(12) = ... = 0 $ 이 된다.

이 값을 먼저 구한다면 $ \mu(x) = 0 $인 $x$에 대해서는 $x^{2}$ 를 무시하면 된다.

 

다음 문제점을 보면 36이란 숫자는 4($\mu(2) != 0)$)의 배수, 9($\mu(3) != 0)$)의 배수, 36($\mu(6) != 0)$)의 배수 등 3곳에서 중복된다. 

아래에서 설명할 포함과 배제의 원리로 4의 배수에서 더해주고, 9의 배수에서 더해주고, 36의 배수에서 빼주면 결국 하나로 카운트할 수 있다. 궁극적으로 전체 개수에서 뺄 거니까 모두 음수 처리를 하자.

 

4($ 2^{2} $)와 9($ 3^{2} $) 에서는 빼고(-1), 36($ 6^{2} $) 에서는 더하는(+1) $ \mu(n) $ 함수를 여기에도 적용해보자.

1. $ \mu(n) = 0 $ (n을 소인수분해했을 때 지수가 2 이상인 소수가 존재)
2. $ \mu(n) = -1 $ (n을 소인수분해했을 때 지수의 합이 홀수)
3. $ \mu(n) = 1 $ (n을 소인수분해 했을때 지수의 합이 짝수)

36의 예를 풀어보면 $\mu(2) = \mu(3) = -1 $, $\mu(6) = 1$로 정의된다.

 

뫼비우스 함수 일반화

이렇게 $ \mu(n) $ 을 정의하고 f(42)를 구했던 방법을 일반화시켜보면 아래와 같다.
$$ f(N) = N + \sum_{i=2}^{N} \mu(i) \lfloor \frac{N}{i^{2}} \rfloor $$

 

약간의 예외로 $ \mu(1) = 1 $ 이라고 정의하면 아래처럼 다시 쓸 수 있다.
$$ f(N) = \sum_{i=1}^{N} \mu(i) \lfloor \frac{N}{i^{2}} \rfloor $$

 

$ \mu(n) $ 만 미리 구해놓는다면 square-free 숫자를 구하는 건 쉽다.

#include<stdio.h>
#define ll long long

int mu[1000010];

void buildMu() {
    mu[1] = 1;
    for(int i = 1; i <= 1000000; i++) {
        for(int j = 2 * i; j <= 1000000; j += i) {
            mu[j] -= mu[i];
        }
    }
}

ll sqFreeCnt(ll n) {
    ll cnt = 0;
    for(ll i = 1; i * i <= n; i++) {
        cnt += mu[i] * (n / (i * i));
    }
    return cnt;
}

int main() {
    buildMu();
    ll maxN, minN;
    scanf("%lld%lld\n", &minN, &maxN);
    printf("%lld\n", sqFreeCnt(maxN) - sqFreeCnt(minN - 1));

    return 0;
}

 

뫼비우스 함수를 미리 만들어 놓는데 그 과정이 마치 에라토스테네스의 체와 같지만 한눈에 이해하기는 좀 힘들다. 뫼비우스 함수 구하는 방법 자체는 어렵지 않으므로 구현보다는 그 의미를 이해하는 게 더 중요하다고 생각한다. 풀이 방법의 흐름을 이해하면 포함과 배제의 원리, $ \mu(n) $ 의 정체인 뫼비우스 함수를 더 쉽게 이해할 수 있다.

 

포함과 배제의 원리

포함과 배제의 원리는 집합 세 개(A, B, C)의 합집합의 크기를 한번 구해보면 무엇을 뜻하고 어떻게 접근해야 할지 대충 감이 온다.
$$ | A \cup B \cup C | = | A | + | B | + | C | - | A \cap B | - | B \cap C | - | C \cap A | + | A \cap B \cap C | $$

 

감이 오지 않는다면 집합 네 개, 다섯 개짜리를 써보면 확실히 느낌이 올 것이다.
1개짜리 집합은 모두 더하고, 2개짜리 집합은 모두 빼고, 3개짜리 집합은 모두 더하고... 를 반복하면 된다.

 

뫼비우스 함수

제곱 인수가 있는 정수인지, 없다면 소인수의 개수가 짝수인지 또는 홀수인지에 따라 {0, -1, 1}을 반환하는 함수이다.
$$ \mu(n) = (-1)^{\sum_{p} n_{p}}\prod_{p}[n_{p}\leq 1] $$