[BOJ 15868] Yule Lads

Yule lads라는 산타클로스(?)가 왜서 불을 끄고 키고 한다는 문제이다. 총 $N$개의 집이 있고 모두 불이 켜져있다. 크리스마스의 $n$째날 전에는 $n$의 배수 번째 집의 불이 꺼지고 마지막에 숫자 1을 제외하고 모든 집에 불이 꺼질 경우 몇 명의 Yule Lads가 올 수 있을까?를 묻고 있다. 이런 경우에는 소수를 먼저 보자. 소수 번째 집에는 반드시 YL(Yule Lad)이 와야한다. 그럼 서로 다른 소수의 곱 번째 집($pq$)에는 $p$가 한 번 왔다가고 $q$가 한번 왔다 가므로 $pq$는 반드시 들러야한다. 일반화해보면 $n$의 약수의 개수가 짝수 개이면 된다는 것이다. 그런데 소수의 제곱수들을 생각해보자. 이들은 약수가 홀수 개이므로 YL이 오지 않는다. 서로 다른 $n$개의 소수의 곱으로 이루어진 square free number $k$와 임의의 소수의 제곱 $p^{2}$의 곱 $m$ 에 대해 생각하자. 전체 약수의 개수는 $3\cdot 2^{n}$ 이다. 이때 제외되는 약수의 개수는 $2^{n}-1$개이다. 이것은 $k$를 이루는 소수의 개수를 1개부터 수학적 귀납법을 이용하면 쉽게 증명할 수 있다. 우리는 약수의 개수가 홀수인지 짝수인지에 관심이 있으니 modulo 2에 대해 생각하도록 하자. 그럼 제시한 $m$에 대해서는 홀수개의 약수가 존재하여 YL이 방문하지 않는다. 그럼 좀 더 많은 개수의 소수의 거듭제곱의 곱들에 대해 생각하자. $m=(p_{1}p_{2}\cdots p_{t})^{2}k$이면 제외되는 약수의 개수는 몇 개일까? 포함 배제의 원리로 생각하면 다음이 됨을 확인할 수 있다.
$$\sum_{i=1}^{t} {t \choose i} (-1)^{i}$$
또한 이 식의 값은 항상 -1임을 알 수 있다. 따라서 square free number가 아닌 수들의 약수의 개수는 홀수가 됨을 확인했다. 따라서 square free number의 개수를 mobius inversion으로 세면 된다.