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

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

#include <bits/stdc++.h>
using namespace std;
ifstream cin("norocos.in");
ofstream cout("norocos.out");
int knorocoase(int n)
{
    int d = 2 , cnt = 0;
    while(n > 1)
    {
        int p = 0;
        while(n % d == 0) p++ , n /= d;
        if(p == 1) cnt++;
        else if(p > 1) return 0;
        d++;
        if(d *d  > n) d = n;
    }
    return cnt;
}

int main()
{
    int cer , n , k , x , min = 2000000001 , max = -2000000001 , cnt = 0;
    cin >> cer >> n >> k;
    if(cer == 1)
    {
        for(int i = 1 ; i <= n ; i++)
        {
            cin >> x;
            if(x % 2 == 1)
            {
                if(x < min) min = x;
                if(x > max) max = x;
            }
        }
        if(min != 2000000001 && max != -2000000001)
            cout << min << " " << max;
        else cout << 0;
    }
    else
    {
       for(int i = 1 ; i <= n ; i++)
        {
            cin >> x;
            if(knorocoase(x) == k) cnt++;
        }
        cout << cnt;
    }

}