Rezolvare PBinfo #1694

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 ≤ 1000
• 2 ≤ k ≤ 30
• 1 ≤ 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