이어진 사이

각 정수의 서로 다른 소인수를 이용하여 연결 컴포넌트를 구한다.

같은 소수 $p$로 나누어떨어지는 정점들은 모두 서로 간선으로 연결되므로 같은 연결 컴포넌트에 속한다. 소수 $p$를 포함하는 정점 중 대표 정점 하나만 기억하면, 이후 $p$를 소인수로 가지는 정점을 그 대표 정점과 합칠 수 있다.

에라토스테네스의 체로 각 정수의 최소 소인수를 전처리한다. 각 $A_i$를 소인수분해하면서 중복되지 않는 모든 소인수 $p$를 확인하고, $p$의 대표 정점과 $i$를 서로소 집합 자료구조로 합친다. $A_i=1$이면 소인수가 없으므로 다른 정점과 합치지 않는다.

임의의 간선 $(i,j)$에 대해서는 $A_i,A_j$에 공통 소인수가 존재하므로 두 정점이 합쳐진다. 반대로 합치기를 수행하는 두 정점은 어떤 소인수를 공유하므로 실제 그래프에서도 간선으로 연결된다. 따라서 서로소 집합의 연결 관계는 원래 그래프의 연결 관계와 정확히 일치한다.

각 질의는 두 정점의 대표가 같은지 확인하여 답한다. $u=v$이면 항상 대표가 같다.

$M=\max A_i$라고 하면, 시간 복잡도는 $O(M\log\log M + N\log M + Q\alpha(N))$, 공간 복잡도는 이다.

Solution written by GPT6