autobuze

Autobuze

== include(page="template/taskheader" task_id="autobuze") ==

Poveste şi cerinţă...

Confuz de transportul in comun, Gigel, locuitor al municipiului Bucuresti, se gandeste sa isi simplifice cumva viata. Dupa un studiu foarte amanuntit al numerelor scrise pe autobuzele din Bucuresti, el isi da seama de urmatorul lucru:
 
* Doua autobuze ce au inscriptionate numerele $A$, respectiv $B$, au acelasi traseu daca $A$ si $B$ au in componenta aceeasi factori primi. De exemplu: autobuzele cu numerele $12 = 2^2^ * 3^1^$, $18 = 2^1^ * 3^2^$, $72 = 2^3^ * 3^2^$ au acelasi traseu, toate trei avand aceeasi factori primi, $2$ si $3$.
 
Nu este asa ca aceasta regula va simplifica si voua viata? Desigur. De aceea, Gigel va intreaba:
 
* Cate trasee diferite exista in Bucuresti?
 
Se dau $N$, numarul de autobuze din Bucuresti, si un sir a ~i~ de $N$ numere naturale, reprezentand numerele inscriptionate pe cele $N$ autobuze. Daca ii raspundeti corect lui Gigel la intrebare, va veti simplifica viata si veti primii $100$ puncte!

h2. Date de intrare

Fişierul de intrare $autobuze.in$ ...

Fişierul de intrare $autobuze.in$ contine pe prima linie numarul natural $N$, iar pe cea de-a doua linie $N$ numere naturale, reprezentand numerele inscriptionate pe cele $N$ autobuze.

h2. Date de ieşire

În fişierul de ieşire $autobuze.out$ ...

În fişierul de ieşire $autobuze.out$ se va gasi un singur numar natural, reprezentand numarul de trasee diferite existente.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 50.000$
* $1 ≤ a ~i~ ≤ 1.000.000.000$

h2. Exemplu

  multiple lines.
|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="autobuze") ==