Rezolvare PBinfo #2863

pyk

Fie k, n și y trei numere naturale. Fie X un șir format din n numere naturale: \( x_1, x_2, x_3, …, x_n \). Fie P produsul numerelor \( y, x_1, x_2, x_3, …, x_n \), adică \( P = y\times x_1\times x_2 \times x_3 \times … \times x_n \). Numărul P este o “k-putere” dacă există un număr natural z astfel încât \( P=z^k \).

Cerințe

Scrieți un program care să citească numerele \( k, n, x_1, x_2, x_3, …, x_n \) și care să determine:

• 1. cel mai mic și cel mai mare număr din șirul X ce sunt formate doar din cifre identice;
• 2. descompunerea în factori primi a celui mai mic număr natural y (y ≥ 2) cu proprietatea că numărul \( P = y\times x_1\times x_2 \times x_3 \times … \times x_n \) este o “k-putere”.

Date de intrare

Fișierul de intrare pyk.in conține:

• pe prima linie, un număr natural C, reprezentând cerința din problemă care trebuie rezolvată (1 sau 2);
• pe a doua linie, numerele naturale k și n, separate printr-un singur spațiu;
• pe a treia linie, cele n numere naturale \( x_1, x_2, x_3, …, x_n \), separate prin câte un singur spaţiu.

Date de ieșire

Dacă C=1, atunci prima linie a fişierului de ieşire pyk.out va conține două numere naturale, separate printr-un
singur spațiu, reprezentând răspunsul la cerința 1 a problemei. Dacă nu există astfel de numere, prima linie a
fișierului va conține valoarea 1.

Dacă C=2, atunci fișierul de ieşire pyk.out va conține:

• pe prima linie, un număr natural m reprezentând numărul de factori primi distincți din descompunerea în
  factori primi a numărului y, determinat la rezolvarea cerinței 2;
• pe fiecare dintre următoarele m linii (câte o linie pentru fiecare factor prim din descompunerea în factori primi
  a lui y), câte două valori F şi E, separate printr-un singur spaţiu, reprezentând factorul prim F și exponentul
  E al acestui factor din descompunerea în factori primi a lui y.

Scrierea în fișier a acestor factori primi se va face în ordinea crescătoare a valorii lor.

Restricții și precizări

• 2 ≤ n ≤ 50.000
• 2 ≤ k ≤ 100
• 2 ≤ \( x_1, x_2, x_3, …, x_n \) ≤ 10.000
• 2 ≤ y
• pentru rezolvarea corectă a cerinței 1 se acordă 10 puncte;
• pentru rezolvarea corectă a cerinței 2 se acordă 90 puncte.

Exemplu:

pyk.in

1
2 7
122 1111 5 4 88 123 999

pyk.out

4 1111 

Explicație

Cerința este 1, k=2, n=7. Numerele din șirul X formate doar din cifre identice sunt: 1111, 5, 4, 88, 999. Cel mai mic număr dintre acestea este 4, iar cel mai mare este 1111.

pyk.in

2
3 6
12 5 60 125 4 36

pyk.out

3
2 1
3 2
5 1

Explicație

Cerința este 2, k=3, n=6. Produsul celor 6 numere din șir este: 12*5*60*125*4*36=64800000. y=90 este cea mai mică valoare pentru care P = 90 * 64800000 = 18003 devine o “k-putere“. Descompunerea în factori primi a lui y conține m=3 factori
primi: \( 2^1\times 3^2\times 5^1 \).