Candale Silviu (silviu) Un număr natural nenul m se numește norocos dacă pătratul lui se poate scrie ca sumă de m numere naturale consecutive. Un număr natural m se numește k-norocos, dacă este egal cu produsul a exact k numere prime distincte. Observați că între cele două proprietăți definite nu există nicio legătură.
Cerința
Dându-se k și N numere naturale, scrieți un program care să determine:
a) Cel mai mic și cel mai mare număr norocos dintre cele N numere citite
b) Câte numere k-norocoase sunt în șirul de N numere citite
Date de intrare
Fișierul de intrare norocos.in conține pe prima linie un număr natural C. Pentru toate testele de intrare, numărul C are una din valorile 1 sau 2. Pe linia a doua a fișierului se găsesc numerele naturale N și k, cu semnificația din enunț, iar pe a treia linie se găsesc N numere naturale, separate prin câte un spațiu.
Date de ieșire
Fișierul de ieșire este norocos.out.
Dacă C=1, se va rezolva numai punctul a). În acest caz, în fişierul de ieşire se vor scrie, separate printr-un spațiu, în această ordine, cel mai mic și cel mai mare număr norocos dintre cele N numere citite. Dacă nu există niciun număr norocos se va afișa valoarea 0. Dacă există un singur număr norocos, acesta se va afișa de două ori.
Dacă C=2, se va rezolva numai punctul b). În acest caz, în fişierul de ieşire se va scrie un singur număr reprezentând numărul de numere k-norocoase citite.
Restricții și precizări
1 ≤ N ≤ 10002 ≤ k ≤ 301 ≤numerele citite de pe a treia linie a fișierului≤ 2 000 000 000- Pentru rezolvarea corectă a primei cerinţe se acordă 40 de puncte, pentru rezolvarea corectă a celei de-a doua cerințe se acordă 60 de puncte.
Exemplul 1
norocos.in
1 9 3 165 12 33 30 5 18 105 15 4
norocos.out
5 165
Explicație
Atenție, C=1, deci se va rezolva doar prima cerință.
Cel mai mic număr norocos este 5
52=25=3+4+5+6+7
Cel mai mare număr norocos este 165
1652=27225=83+84+85+…+246+247
Observați faptul că, deși se citește valoarea lui k, aceasta nu este folosită în rezolvarea cerinței 1.
Exemplul 2
norocos.in
2 5 3 165 31 165 105 44
norocos.out
3
Explicație
Atenție, C=2, deci se va rezolva doar a doua cerință.
Cele trei numere k-norocoase sunt 165, 165, 105