pyk

Fie $k$, $n$ și $y$ trei numere naturale.
Fie $X$ un șir format din $n$ numere naturale: $x_1, x_2, x_3, \ldots, x_n$.
Fie $P$ produsul numerelor $y, x_1, x_2, x_3, \ldots, x_n$, adică: $P = y \cdot x_1 \cdot x_2 \cdot x_3 \cdot \ldots \cdot x_n$.

Numărul $P$ este o “$k$-putere” dacă există un număr natural $z$ astfel încât $P=z^k$.

Cerință

Scrieţi un program care să citească numerele $k$, $n$, $x_1$, $x_2$, $x_3$, $\dots$, $x_n$ şi care să determine:

1. Cel mai mic număr și cel mai mare număr din șirul $X$, formate doar din cifre identice;
2. Descompunerea în factori primi a celui mai mic număr natural $y$ ($y \geq 2$) cu proprietatea că numărul $P = y \cdot x_1 \cdot x_2 \cdot x_3 \cdot \ldots \cdot 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, \dots, 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 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 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 \leq n \leq 50 \ 000$;
• $2 \leq k \leq 100$;
• $2 \leq x_1, x_2, x_3, \dots, x_n \leq 10 \ 000$;
• $2 \leq y$;
• Pentru rezolvarea corectă a cerinţei $1$ se acordă $10$ puncte;
• Pentru rezolvarea corectă a cerinței $2$ se acordă $90$ de puncte.

Exemplul 1

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$.

Exemplul 2

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 \cdot 5 \cdot 60 \cdot 125 \cdot 4 \cdot 36 = 64800000$.

$y=90$ este cea mai mică valoare pentru care $P=90 \cdot 64800000 = 1800^3$ devine o “$k$-putere“.

Descompunerea în factori primi a lui $y$ conține $m=3$ factori primi: $2^1 \cdot 3^2 \cdot 5^1$