Cupa InfoAs, ediția 3 · Clasa a IX-a Vectori (tablouri unidimensionale) Vectori de frecvență și vectori caracteristici
Problema Parola de WiFi
Radu a devenit major! După o petrecere cum se cuvine, s-a trezit a doua zi la primărie pentru a-și schimba buletinul. Mare a fost supărarea lui când a văzut că are de așteptat trei ore la coadă. Plictisit și rupt de oboseală, Radu a decis să se conecteze la internet pentru a asculta niște muzică, însă când să ceară parola de la Wi-Fi, doamna de la biroul de informații i-a dat o problemă de informatică, unde răspunsul reprezintă chiar parola de internet.
Cum Radu nu știe informatică, te roagă pe tine să îi afli cât de repede posibil parola de internet, rezolvând problema de mai jos!
Cerință
Problema primită de Radu este următoarea. Se dă un șir de n numere naturale, cu proprietatea că toți divizorii lor primi sunt numere naturale de o cifră. Să se determine numărul de secvențe de elemente aflate pe poziții consecutive din șirul dat, cu proprietatea că produsul numerelor un cub perfect.
Date de intrare
Pe prima linie a fișierului de intrare parola.in se află numărul natural n, reprezentând numărul de elemente ale șirului. Pe a doua linie se află cele n elemente numere naturale, separate prin câte un spațiu.
Date de ieșire
Fișierul de ieșire parola.out va conține un singur număr natural reprezentând numărul de secvențe de elemente de pe poziții consecutive din șir care au produsul elementelor un cub perfect.
Restricții și precizări
1 ≤ n ≤ 100.0001 ≤ cele n numere ≤ 1.000.000.000
Pentru 30 de puncte
1 ≤ n ≤ 10001 ≤ cele n numere ≤ 10.000.000
Pentru alte 70 de puncte
- Restricțiile inițiale ale problemei
Exemplu
6 10 8 25 9 12 18
3
Explicația exemplului
În șirul (10, 8, 25, 9, 12, 18) avem 3 secvențe cu produsul un cub perfect. Acestea sunt (10, 8, 25, 9, 12), cu produsul 603, (8), cu produsul 23 și (12, 18), cu produsul 63.
Problemă adăugată pe InfoAs de 
cout << "Suma este " << s;