BOJ 14859 세 쌍 서로수

문제 링크

14859번: 세 쌍 서로소

\(\text{MAX} = 10^6\) 범위의 수가 \(n\) 개 주어져 있고, 이 중에서 \(\gcd\)가 1인 triplet의 개수를 구하는 문제이다.

---

썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다.

 

 

 

 

 

 

 

 

---

이 문제는 포함-배제 원리를 이용해서 해결할 수 있다. \(\gcd\)가 \(g\)인 triplet의 개수를 \(A(g)\), \(\gcd\)가 \(g\)의 배수인 triplet의 개수를 \(B(g)\)라고 하면 다음의 관계식이 성립한다. \(p,q,r...\)은 전부 prime이다.

 

$$ A(g) = B(g) - \sum_{p} B(pg) + \sum_{p < q} B(pqg) - \sum_{p < q < r} B(pqrg) + \cdots = \sum_{k=1}^{\text{MAX}/g} \mu(k) B(kg) $$

 

이 문제에서 원하는 건 \(A(1)\)이므로 사실상 \(\displaystyle \sum_{k=1}^{MAX} \mu(k) B(k)\)를 구하면 된다.

\(\mu\)는 Mobius function으로, 약-배수 관계를 이용한 포함 배제 원리를 적용할 때 유용하다.

 

\(B(g)\)는 naive하게 모든 \(g\)의 배수의 count값을 다 더한 후 \(\displaystyle \begin{pmatrix} \cdot \\ 3 \end{pmatrix}\)에 넣어주면 된다. 모든 \(g\)에 대해서 이 과정을 수행한다고 해도 연산 횟수는 \(\mathcal{O}(MAX + \frac{MAX}{2} +\frac{MAX}{3} + \cdots = MAX \ln MAX)\)다.

 

Mobius function은 에라토스테네스의 체를 돌리면서 구하는 방법도 있지만 사실 하나의 routine으로도 충분하다.

\(n > 1\)에 대해 \(\displaystyle \sum_{d | n} \mu(d) = 0\)이기 때문에, \(\displaystyle \mu(n) = \sum_{d | n} -\mu(d)\)가 성립한다. 그래서 \(\mu[1] = 1\)로 초기화해놓고, 반복문을 하나 돌리면서 모든 \(i\)의 배수에 \(j\)에 대해 \(\mu[j] \leftarrow \mu[j] - \mu[i]\)같은 루틴을 실행하면 역시 \(O(MAX \ln MAX)\)이다.

 

두 카운트 배열을 for문 하나로 묶을 수 있기 때문에 코드가 굉장히 짧다.