Server Cluster Size

# Server Cluster Size ## Problem Statement You are given an array $a$ of $n$ positive integers, where $a_i$ represents a property of the $i$-th server ($0$-indexed). A network of servers is formed based on these properties. Two distinct servers at indices $i$ and $j$ are considered **connected** if the greatest common divisor (${GCD}$) of their properties, $a_i$ and $a_j$, is greater than $1$. That is, if ${GCD}(a_i, a_j) > 1$. This connectivity relation is transitive: if server $A$ is connected to server $B$, and server $B$ is connected to server $C$, then server $A$ is also considered connected to server $C$. This forms connected components, which we refer to as **clusters**. Your task is to determine the size of the cluster to which each server belongs. You should return an array of $n$ integers, where the $k$-th value in the array ($0$-indexed) is the total number of servers in the cluster containing server $k$. ## Input Format - The first line contains a single integer $n$ ($1 \le n \le 10^5$), representing the number of servers. - The second line contains $n$ space-separated integers $a_0, a_1, \ldots, a_{n-1}$ ($1 \le a_i \le 10^5$), representing the properties of the servers. ## Output Format Print $n$ space-separated integers. The $k$-th integer should be the size of the cluster to which server $k$ belongs. ## Sample Test Cases ### Sample Input 1 ``` 3 3 3 3 ``` ### Sample Output 1 ``` 3 3 3 ``` ### Sample Input 2 ``` 5 2 3 6 1 5 ``` ### Sample Output 2 ``` 3 3 3 1 1 ``` ## Constraints - $1 \le n \le 10^5$ - $1 \le a_i \le 10^5$ - Time limit: 1 second - Memory limit: 256 MB ## Explanation ### Sample 1: Given $n=3$ and $a = [3, 3, 3]$. - For servers $0$ and $1$: $\text{GCD}(a_0, a_1) = \text{GCD}(3, 3) = 3 > 1$. They are connected. - For servers $0$ and $2$: $\text{GCD}(a_0, a_2) = \text{GCD}(3, 3) = 3 > 1$. They are connected. - For servers $1$ and $2$: $\text{GCD}(a_1, a_2) = \text{GCD}(3, 3) = 3 > 1$. They are connected. All servers are connected to each other, forming a single cluster of size $3$. Thus, each server belongs to a cluster of size $3$. ### Sample 2: Given $n=5$ and $a = [2, 3, 6, 1, 5]$. - Consider server $0$ ($a_0=2$): - With server $1$ ($a_1=3$): $\text{GCD}(2, 3) = 1$. Not connected. - With server $2$ ($a_2=6$): $\text{GCD}(2, 6) = 2 > 1$. Connected. - With server $3$ ($a_3=1$): $\text{GCD}(2, 1) = 1$. Not connected. - With server $4$ ($a_4=5$): $\text{GCD}(2, 5) = 1$. Not connected. - Consider server $1$ ($a_1=3$): - With server $2$ ($a_2=6$): $\text{GCD}(3, 6) = 3 > 1$. Connected. - (Already checked with server $0$) - Server $2$ ($a_2=6$) is connected to server $0$ ($a_0=2$) and server $1$ ($a_1=3$). Servers $0, 1, 2$ form a cluster because $0$ is connected to $2$, and $1$ is connected to $2$. By transitivity, they are all in the same cluster. The size of this cluster is $3$. - Server $3$ ($a_3=1$): - $\text{GCD}(1, x) = 1$ for any $x$. So, server $3$ is not connected to any other server. It forms a cluster of size $1$. - Server $4$ ($a_4=5$): - Not connected to $0, 1, 2, 3$. It forms a cluster of size $1$. The cluster sizes for servers $0, 1, 2, 3, 4$ are $3, 3, 3, 1, 1$ respectively.