FMI NO STRESS 13 | Friendly Numbers

This was the problem page during the contest. Access the current page here.
Time limit: 0.05s Memory limit: 256MB Input: Output:

Cerință

Marcel a primit de la bunica sa un sac cu bile care au numere naturale inscripționate pe ele. Bunica sa, Bogdana, i-a spus că unele bile sunt prietenoase, iar unele mai puțin prietenoase, și l-a învățat și cum să își dea seama. Un număr se numește prietenos dacă, în descompunerea sa în factori primi, toți exponenții sunt egali. O bilă se numește prietenoasă dacă are inscripționată pe ea un număr prietenos. De exemplu:

  • Bila cu numărul 27000=23335327000 = 2^3 \cdot 3^3 \cdot 5^3 este prietenoasă.
  • Bila cu numărul 30184=23331130184 = 2^3 \cdot 3^3 \cdot 11 nu este prietenoasă.

Marcel se întreabă care este procentul ca extrăgând o singură bilă din sacul primit, aceasta să fie prietenoasă.

Date de intrare

Pe prima linie se găsește un număr natural NN, care reprezintă numărul de bile din sacul primit, iar pe următoarea linie se găsesc NN numere naturale care sunt numerele inscripționate pe bile.

Date de ieșire

Pe prima linie se va găsi un număr natural, care reprezintă procentul ca bila extrasă să fie prietenoasă. Se cere partea întreagă a acestuia. 57.64%=57%\lfloor 57.64\% \rfloor = 57\%

Restricții și precizări

  • 1N100 0001 \leq N \leq 100 \ 000;
  • 1xi100 0001 \leq x_i \leq 100 \ 000.

Exemplul 1

stdin

11
1 2 3 4 5 6 7 8 9 10 11

stdout

100

Explicație

Toate numerele sunt prietenoase.

  • 2,3,5,7,112, 3, 5, 7, 11 sunt numere prime, deci sunt prietenoase.
  • 11 este de asemenea prietenos.
  • 4=224 = 2^2 are un singur exponent, deci este prietenos.
  • 6=21316 = 2^1 \cdot 3^1 are coeficienții egali cu 11.
  • 9=329 = 3^2 are un singur exponent, deci este prietenos.
  • 10=215110 = 2^1 \cdot 5^1 are coeficienții egali cu 11.

Exemplul 2

stdin

9
12 18 20 24 28 40 44 45 48

stdout

0

Explicație

Niciun număr nu este prietenos.

Exemplul 3

stdin

7
1 12 9 48 7 7 12

stdout

57

Log in or sign up to be able to send submissions!