ID #123 · Colecția InfoAs · Operatori și expresii

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.000` * `1 ≤ cele n numere ≤ 1.000.000.000` ### Pentru 30 de puncte * `1 ≤ n ≤ 1000` * `1 ≤ cele n numere ≤ 10.000.000` ### Pentru alte 70 de puncte * Restricțiile inițiale ale problemei