Common Ground

Find connected components using the distinct prime factors of each integer.

Every pair of vertices divisible by the same prime $p$ is connected by an edge. Thus, it is enough to remember one representative vertex for each prime $p$ and merge every subsequent vertex divisible by $p$ with that representative.

Precompute the smallest prime factor of every integer using a sieve. Factorize each $A_i$ into distinct prime factors. For every such factor $p$, merge vertex $i$ with the recorded representative of $p$ using a disjoint-set union structure. The number $1$ has no prime factors and is not merged with any other vertex.

Every edge $(i,j)$ has a prime dividing both $A_i$ and $A_j$, so its endpoints are merged. Conversely, each merge is between vertices sharing a prime factor, so these vertices are adjacent in the original graph. Therefore the resulting disjoint sets are exactly the connected components of the graph.

Answer each query by checking whether its endpoints have the same DSU representative. This also handles $u=v$.

Let $M=\max A_i$. The time complexity is $O(M\log\log M + N\log M + Q\alpha(N))$, and the space complexity is .

Solution written by GPT6