Pracsiu Dan (dnprx) Un număr puternic este un număr natural mai mare decât 1 care are proprietatea că dacă este divizibil cu numărul prim p atunci este divizibil și cu p2. De exemplu, 36 și 27 sunt numere puternice, în timp ce 12 nu este număr puternic deoarece este divizibil cu 3 și nu este divizibil cu 32. La ora de matematică elevii au aflat ce înseamnă un număr puternic. Pentru a verifica dacă elevii au înțeles, domnul profesor a scris pe tablă un șir de N numere naturale X1, X2, …, XN și l-a rugat pe Mihai să ștergă din șir numerele puternice.
Analizând numerele rămase, Mihai a observat că se poate obține un număr puternic prin concatenarea a două numere din șirul rămas, numere egal depărtate de capetele acestui nou șir. Concatenarea presupune lipirea numărului din a doua jumătate a șirului la finalul celui aflat în prima jumătate. Dacă noul șir are număr impar de elemente, elementul din mijloc se ignoră. De exemplu, dacă șirul obținut după ștergerea numerelor puternice este: 12, 1, 19, 13, 3, 21, 5 atunci numerele obținute prin concatenare sunt 125, 121, 193.
Cerință
Scrieți un program care citește un număr natural N și apoi un șir de N numere naturale și determină:
1. Câte numere puternice sunt în șirul dat;
2. Care sunt perechile de numere din șirul rămas după ștergerea numerelor puternice, numere egal departate de capetele șirului, prin concatenarea cărora se obține un număr puternic.
Date de intrare
Fișierul de intrare puternic.in conține pe prima linie un număr natural C. Pentru toate testele de intrare, numărul C poate avea doar valoarea 1 sau 2. Pe a doua linie a fișierului se găsește numărul natural N. Pe a treia linie se găsesc N numere naturale separate prin câte un spațiu.
Date de ieșire
Dacă C = 1, se va rezolva cerința 1. În acest caz, fișierul de ieșire puternic.out va conține pe prima linie un număr natural reprezentând numărul de numere puternice din șirul dat.
Dacă C = 2, se va rezolva cerința 2. În acest caz, fișierul de ieșire puternic.out va conține perechile de numere egal depărtate de capetele șirului obținut după ștergere, prin concatenarea cărora de obține un număr puternic. Fiecare pereche se scrie pe câte un rând, iar numerele din pereche se scriu separate printr-un spațiu, primul număr fiind cel din stânga. Dacă sunt mai multe astfel de perechi se vor afișa, în ordine, începând cu cea apropiată de capetele noului șir. Dacă nu există nicio astfel de pereche, în fișierul puternic.out se va afișa -1.
Restricții și precizări
1 ≤ N ≤ 100.0001 ≤ X1,X2, …,XN≤ 1.000.000.000- Pentru rezolvarea corectă a primei cerințe se obțin 30 de puncte, iar pentru rezolvarea corectă a celei de a doua cerințe se obțin 70 de puncte.
Exemplul 1:
puternic.in
1 8 100 28 16 11 484 25 162 27
puternic.out
5
Explicație
Se rezolva prima cerință. Numerele puternice sunt 100 16 484 25 27.
Exemplul 2:
puternic.in
2 11 12 9 1 8 19 6 3 4 49 21 5
puternic.out
12 5 1 21
Explicație
Se rezolvă a doua cerință și se va folosi doar valoarea N. După ștergerea numerelor puternice, șirul rămas este: 12 1 19 6 3 21 5.