백준 1557 제곱 ㄴㄴ 문제 풀이
이 문제는 뫼비우스 함수를 사용하여 Square-free Integer(SFI)를 다뤄야 합니다. 뫼비우스 함수를 어떻게 사용할 수 있는지 알 수 있는 좋은 문제이지만, 아직까지 그 외에 뫼비우스 함수 자체를 가져다 쓸 수 있는 사례는 찾지 못했습니다.
문제 파악하기
1부터 시작하여 K번째 SFI를 찾는 문제입니다. 무작정 모든 수를 훑으며 SFI인지 여부를 파악하기에는 K가 최대 10억입니다. 1부터 K까지의 모든 수가 SFI는 아닐테니, 실제로 10억이 입력으로 주어지면 그보다 더 큰 수까지 훑어야 할 것입니다.
문제 풀어보기
1부터 N 사이의 SFI의 개수를 계산하면 문제에 활용할 수 있을 것 같습니다. 1부터 N 사이의 SFI의 개수를 $C_N$이라고 정의하고, $C_{67}$을 계산해봅시다.
우선, 67 이하의 수 중 제곱수의 배수의 개수를 찾아보고자 합니다.
- $2^2=4$의 배수는 1부터 67 사이에 $\lfloor \frac{67}{4} \rfloor = 16$, 16개 존재.
- $3^3=9$의 배수는 1부터 67 사이에 $\lfloor \frac{67}{9} \rfloor = 7$, 7개 존재.
- $4^4=16$의 배수는 1부터 67 사이에 $\lfloor \frac{67}{16} \rfloor = 4$, 4개 존재.
- $5^5=25$의 배수는 1부터 67 사이에 $\lfloor \frac{67}{25} \rfloor = 2$, 2개 존재.
- $6^6=36$의 배수는 1부터 67 사이에 $\lfloor \frac{67}{36} \rfloor = 1$, 1개 존재.
- $7^7=49$의 배수는 1부터 67 사이에 $\lfloor \frac{67}{49} \rfloor = 1$, 1개 존재.
- $8^8=64$의 배수는 1부터 67 사이에 $\lfloor \frac{67}{64} \rfloor = 1$, 1개 존재.
67 이하의 제곱수의 배수의 개수는 31(16 + 7 + 4 + 2 + 1 + 1 + 1)개가 아닙니다. 36의 배수의 경우 이미 4의 배수, 9의 배수, 36의 배수에서 각각 1회씩 카운트했습니다.
\[|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |B \cap C| + |C \cap A| - (|A \cap B \cap C|))\]따라서 마치 합집합을 계산하듯이 포함 배제 처리를 계속해서 해주어야합니다. 합집합의 원소의 개수를 구하고자 할 때, 우리는 각 집합의 원소의 개수와 각 교집합의 원소의 개수를 빼고 더하길 반복합니다.
\[\mu (n) = \begin{cases} 1 & \text{(n=1)} \\ (-1)^{\omega (n)} & \text{(n is square-free integer)} \\ 0 & \text{(otherwise)} \end{cases}\]마찬가지로 $C_N$을 구하는데 있어서 계산 과정에서 수를 계속 더하고 빼주어야 합니다.
뫼비우스 함수는 SFI에 대해 소인수의 개수에 따라 -1, 1이 계속 변화하므로 포함 배제 원리에 쉽게 활용할 수 있습니다. 36의 경우, $\mu(2) + \mu(3) + \mu(6) = (-1) + (-1) + 1 = -1$ 이므로 36이 여러번 세어지지 않고 한번만 세어짐을 확인할 수 있습니다.
정리하자면 어떤 수 N에 대해서, N 이하의 수 중 제곱수의 배수의 개수는 다음과 같이 계산할 수 있습니다.
\[-\sum_{i=2}^{n}{ \mu(i) \lfloor \frac{n}{i^2} \rfloor}\]제곱수의 배수의 개수는 1부터 N 사이의 SFI의 개수인 $C_N$을 찾기 위해 구한 것이므로, $C_N$을 구하는데 다음과 같이 사용할 수 있습니다.
\[C_N = N -(-\sum_{i=2}^{N}{ \mu(i) \lfloor \frac{N}{i^2} \rfloor}) \\ = N + \sum_{i=2}^{N}{ \mu(i) \lfloor \frac{N}{i^2} \rfloor}\]뫼비우스 함수만 구한다면 SFI를 구할 수 있으므로 뫼비우스 함수를 구현해야 합니다. 뫼비우스 함수의 구현은 함수의 성질을 사용하여 구현할 수 있습니다.
\[\sum_{d \vert n}{\mu(d)} = \begin{cases} 1 & \text(n = 1) \\ 0 & \text(n > 1) \end{cases} \\ \mu (n) = \begin{cases} 1 & \text(n = 1) \\ - \sum_{d \vert n, d \ne n} {\mu(d)} & \text(n > 1) \end{cases}\]1
2
3
4
5
6
7
8
9
10
11
12
13
mobius: list[int] = [0, 1] + [-1] * MAX
def compute_mobius() -> list[int]:
for i in range(1, MAX):
for j in range(2 * i, MAX, i):
mobius[j] -= mobius[i]
return mobius
def compute_c_n(n) -> int:
counts = 0
for i in range(1, n // i + 1):
counts += mobius[i] * (n // (n * i))
return counts
힘겹게 뫼비우스 함수를 사용해냈지만, 여전히 최대 입력은 10억이 넘으므로 값을 찾아내려면 이분탐색으로 compute_c_n()을 계속해서 호출해야합니다.