오비탈이 싫어

정수 $x$의 소인수분해에서 지수가 홀수인 소수들의 곱을 $s(x)$라고 하자. 예를 들어 $x=s(x)q^2$가 되며, $s(x)$는 제곱 인수를 가지지 않는다.

$x$가 오비수일 필요충분조건은 $s(x)=2$이다. 또한 두 수 $x,y$에 대해 $xy$가 오비수일 필요충분조건은 $s(x)$와 $s(y)$가 소수 $2$의 포함 여부만 다르고 나머지 소수의 포함 여부가 모두 같은 것이다. 따라서 $s(x)=t$일 때 충돌하는 값은 $t$가 짝수이면 $t/2$, 홀수이면 $2t$이다.

먼저 $s(A_i)=2$인 원소는 혼자서도 오비수이므로 반드시 지워야 한다. 나머지 원소들은 같은 $s(A_i)$ 값을 가진 원소끼리는 서로 충돌하지 않고, $t$와 위에서 정의한 짝 값 사이에서만 충돌한다. 그러므로 각 쌍마다 두 그룹 중 하나의 그룹만 남길 수 있으며, 더 작은 그룹을 지우는 것이 최적이다.

모든 $A_i$를 소인수분해하여 $s(A_i)$를 구하고, 각 값의 개수를 센다. $s(A_i)=2$인 원소 수를 답에 더한 뒤, 남은 값들을 아직 처리하지 않은 쌍끼리 묶어 각 쌍의 작은 개수를 답에 더하면 된다.

$A_i \leq 10^9$이므로 $\sqrt{A_i}$ 이하의 소수들로 충분히 소인수분해할 수 있다. 시간 복잡도는 $O(N\pi(\sqrt{10^9}))$이고, 메모리 복잡도는 $O(N)$이다.

Solution written by GPT5.5