Editing 2863 - Pyk

==pyk==
Fie k, n și y trei numere naturale. Fie X un șir format din n numere naturale: x1,x2,x3,…,xn. Fie P produsul numerelor y,x1,x2,x3,…,xn, adică P=y×x1×x2×x3×…×xn. Numărul P este o “k-putere” dacă există un număr natural z astfel încât P=zk.

==Cerinta==
Scrieți un program care să citească numerele k,n,x1,x2,x3,…,xn
 ș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×x1×x2×x3×…×xn
 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 x1,x2,x3,…,xn, 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 ≤  x1,x2,x3,…,xn
 ≤ 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: 21×32×51.

==Rezolvare==
<syntaxhighlight lang="python3" line="1">
def factorize(num):

   factors = {}
   i = 2
   while i * i <= num:
       while num % i == 0:
           if i not in factors:
               factors[i] = 0
           factors[i] += 1
           num //= i
       i += 1
   if num > 1:
       factors[num] = 1
   return factors

def k_power_factors(k, numbers):

   product = 1
   for num in numbers:
       product *= num
   factors = factorize(product)
   k_factors = {key: value * k for key, value in factors.items()}
   return k_factors

def identical_digits_numbers(numbers):

   identical_numbers = [num for num in numbers if len(set(str(num))) == 1]
   return identical_numbers
Citire date de intrare

C = int(input()) k, n = map(int, input().split()) numbers = list(map(int, input().split()))

if C == 1:

   identical_numbers = identical_digits_numbers(numbers)
   if identical_numbers:
       print(min(identical_numbers), max(identical_numbers))
   else:
       print("1")

elif C == 2:

   k_factors = k_power_factors(k, numbers)
   distinct_factors = sorted(k_factors.keys())
   print(len(distinct_factors))
   for factor in distinct_factors:
       exponent = k_factors[factor]
       print(factor, exponent)
</syntaxhighlight>