백준 1557 제곱 ㄴㄴ 문제 풀이
백준 온라인 저지, 1557번: 제곱 ㄴㄴ
도입
이 문제는 뫼비우스 함수를 사용하여 Square-free Integer(SFI)를 다뤄야 한다.
뫼비우스 함수를 어떻게 사용할 수 있는지 알 수 있는 좋은 문제이지만, 아직까지 그 외에 뫼비우스 함수 자체를 가져다 쓸 수 있는 사례는 찾지 못했다.
문제 파악하기
1부터 시작하여 $K$번째 SFI를 찾는 문제이다. 무작정 모든 수를 훑으며 SFI인지 여부를 파악하기에는 $K$가 최대 10억이다. 1부터 $K$까지의 모든 수가 SFI는 아닐테니, 실제로 10억이 입력으로 주어지면 그보다 더 큰 수까지 훑어야 할 것이다.
문제 풀어보기
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()을 계속해서 호출해야한다.