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

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)