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)