Coprime Components

All submissions for this problem are available.
###Read problems statements [Hindi](http://www.codechef.com/download/translated/OCT18/hindi/CPCOMP.pdf) ,[Bengali](http://www.codechef.com/download/translated/OCT18/bengali/CPCOMP.pdf) , [Mandarin chinese](http://www.codechef.com/download/translated/OCT18/mandarin/CPCOMP.pdf) , [Russian](http://www.codechef.com/download/translated/OCT18/russian/CPCOMP.pdf) and [Vietnamese](http://www.codechef.com/download/translated/OCT18/vietnamese/CPCOMP.pdf) as well. Consider an undirected graph $G$ with $N$ vertices, numbered $1$ through $N$. You are given an integer sequence $A_1, A_2, \dots, A_N$ describing the edges of this graph — for each pair of vertices $u$ and $v$, there is an edge between those vertices if and only if $A_u$ and $A_v$ are coprime. Find the number of connected components of $G$. ### Input  The first line of the input contains a single integer $N$.  The second line contains $N$ spaceseparated integers $A_1, A_2, \dots, A_N$. ### Output Print a single line containing one integer — the number of connected components. ### Constraints  $1 \le N \le 2 \cdot 10^5$  $1 \le A_i \le 2 \cdot 10^5$ for each valid $i$ ### Subtasks **Subtask #1 (5 points):** $1 \le N \le 500$ **Subtask #2 (25 points):** $1 \le N \le 5,000$ **Subtask #3 (70 points):** original constraints ### Example Input ``` 5 6 2 3 24 10 ``` ### Example Output ``` 3 ``` ### Explanation There are two edges $(2, 3)$ and $(3, 5)$. There are $3$ connected components $(1)$, $(2, 3, 5)$ and $(4)$.Author:  bciobanu 
Editorial  https://discuss.codechef.com/problems/CPCOMP 
Tags  bciobanu, dsu, graphs, mediumhard, numbertheory, oct18 
Date Added:  16092018 
Time Limit:  0.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions