Fișierul intrare/ieșire	5div2.in, 5div2.out	Sursă	Concurs IQ Academy
Autor	Victor Manz	Adăugată de	Victor Manz • vmanz
Timp de execuție pe test	0.05 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	1.5

Vezi soluțiile trimise | Statistici

5div2

Dacă \(x=\left( x_{0},x_{1},..,x_{n-1} \right)\) este un șir de numere naturale, numim secvență a lui x un subșir al său format doar din termeni aflați pe poziții consecutive în x. De exemplu, dacă x = (5, 18, 13, 20, 116, 82), atunci (5, 18, 13), (20), (13, 20, 116, 82) sunt secvențe ale lui x, dar (18, 20, 116), (115, 82) și (13, 116, 20) nu sunt secvențe ale șirului.

Se dă un șir \(x=\left( x_{0},x_{1},..,x_{n-1} \right)\) de numere naturale și se cere:

• numărul termenilor șirului x care au exact 5 divizori
• numărul de secvențe echilibrate ale șirului x, adică numărul secvențelor care au exact jumătate din termeni numere care au câte 5 divizori

Date de intrare

Din fișierul de intrare 5div2.in se vor citi:

• de pe prima linie a fișierului c = numărul cerinței care trebuie rezolvată
• de pe a doua linie a fișierului n = numărul termenilor șirului x
• de pe a treia linie a fișierului termenii șirului \(x=\left( x_{0},x_{1},..,x_{n-1} \right)\) separați prin câte un spațiu.

Date de ieșire

În fișierul de ieșire 5div2.out se va afișa un singur număr:

• dacă c = 1: numărul termenilor șirului x care au exact 5 divizori
• dacă c = 2: numărul de secvențe echilibrate ale șirului x.

Restricții

• \( c\in \left\{ 1,2 \right\} \)
• 1 ≤ n ≤ 100 000
• \( 0\le x_{i}\le 10^{18} \)
• șirul x este ordonat crescător, adică \( x_{i-1} \le x_{i} \forall i, 1\le i\le n-1 \)
• se acordă 44 % din punctaj pentru rezolvarea cerinței 1 și 56 % din punctaj pentru rezolvarea cerinței 2

Exemplu

5div2.in	5div2.out
1 5 16 32 40 625 10000	2
2 5 16 32 40 625 10000	4

Explicație

• în primul exemplu șirul conține 2 numere care au câte 5 divizori: 16 și 625
• în al doilea exemplu șirul conține 4 secvențe echilibrate: aceste sunt: (16,32), (16,32,40,625), (40,625) și (625,10000).