[BOJ 18718] Bags of Candies

이 문제는 $\{1,\cdots,n\}$까지의 수 중에서 $\gcd(i,j)>1$을 만족하는 $(i,j)$ 쌍들을 최대한 많이 만들고 쌍을 만들 수 없는 경우 자기 자신이 쌍이 될 때 최소의 쌍의 개수가 몇 개인지 구하는 것이다. 우리는 $p>N/2$이면 $p$는 쌍을 만들 수 없다는 사실을 안다. 다음과 같은 과정을 생각해보자.

$\{1\cdots n\}$에서 쌍이 완벽히 지어졌다 가정하자. 우리는 $n+1$을 저 집합에 추가하고 최적의 쌍을 얻어낼 것이다.

0. $n+1$이 소수이다. 

- $(n+1,n+1)$을 쌍으로 한다.

1. $\{1\cdots n\}$ 중에서 짝지어지지 않은 소수 $p$가 존재하여 $p|n+1$이다.

- $(p,n+1)$을 쌍으로 한다. 

2. $\{1\cdots n\}$에서 $p>N/2$인 소수와 1을 제외한 모든 수들이 쌍으로 묶여있다. 

- $(n+1, n+1)$을 쌍으로 한다.

3. $\{1\cdots n\}$에서 $p>N/2$인 소수와 1, 그리고 합성수 $\alpha$를 제외한 모든 수들이 쌍으로 묶여있다.

-  $\alpha$의 최소인수를 $p$, $n+1$의 최소인수를 $q$라고 하자. $p>\sqrt{N}$이라 가정하자. 그럼 $p^{2}>N$인데 $\alpha$가 합성수라는 조건에 모순이다. 따라서 $p,q\le\sqrt{N}$이고 $pq\le N$이다. 즉, $(pq,\beta)$라는 쌍이 존재한다. $\beta$는 $p$의 배수거나 $q$의 배수임이 분명하다. $p|\beta$이면 $(pq,n+1)$과 $(\beta,\alpha)$를 쌍으로 하자. $q|\beta$이면 $(pq,\alpha)$와 $(\beta,n+1)$을 쌍으로 하자. 

 

위 과정을 따르게 된다면 항상 최소 개수의 쌍을 유지할 수 있다. 여기에서 알 수 있는 것은 $1$과 $p>N/2$인 소수들을 제외한 모든 수들은 짝이 지어진다는 것이다. 따라서 $n$까지 소수의 개수를 $\pi(n)$이라고 하면 우리가 구하고자 하는 최소 쌍의 개수는 다음과 같다.

$$\pi(N)-\pi(N/2)+1+\left\lfloor \frac{N-\pi(N)+\pi(N/2) - 1}{2}\right\rfloor$$

다만 $N-\pi(N)+\pi(N/2) - 1$가 홀수가 되는 경우 1을 더해야 한다. pair가 안맞는 친구가 1개 존재한다는 뜻이기 때문에 그 친구는 혼자서 pair가 된다. 

쿼리가 총 5번 들어오므로 각 퀴리를 $O(N^{2/3})$에 처리하면 될 것이다. 이것은 Lucy-Hedgehog를 효율적으로 구성하면 된다. DB를 제작해서 하는 풀이도 있지만 컴퓨터가 아파해서 안될 것 같다.