2306 - Numere 22
De la Universitas MediaWiki
Cerinţa
Se dau două numere prime p, q și n numere naturale nenule. Determinați exponentul maxim E pentru care numărul pE⋅qE divide produsul celor n numere date.
Date de intrare
Programul citește de la tastatură numere p q n, iar apoi n numere naturale, separate prin spaţii.
Date de ieşire
Programul afișează pe ecran numărul E, reprezentând numărul cerut.
Restricții și precizări
- 1 ≤ n ≤ 1000
- cele n numere citite vor fi mai mici decât 1.000.000.000
Exemplu
- Intrare
- 7 2 5
72 56 70 9 700
- Ieșire
- 3
Rezolvare
import math
def validare_date(p, q, n):
"""
Verifică dacă valorile de intrare sunt valide, bazate pe anumite restricții.
Returnează True dacă sunt valide, False altfel.
"""
if not (2 <= p <= 10**9):
return False
if not (2 <= q <= 10**9):
return False
if not (1 <= n <= 10**5):
return False
return True
def calculeaza_puteri(p, q, n, nums):
p1 = p2 = 0
for tmp in nums:
d = 2
while d * d <= tmp:
p = 0
while tmp % d == 0:
tmp //= d
p += 1
if d == p:
p1 += p
if d == q:
p2 += p
d += 1
if tmp > 1:
if tmp == p:
p1 += 1
elif tmp == q:
p2 += 1
return min(p1, p2)
if __name__ == '__main__':
# citeste valorile de intrare
p, q, n = map(int, input().split())
nums = list(map(int, input().split()))
# valideaza valorile de intrare
if validare_date(p, q, n):
# calculeaza puterile si afiseaza rezultatul
result = calculeaza_puteri(p, q, n, nums)
print(result)
print("\nDatele de intrare corespund restricțiilor impuse.\n")
else:
print("Datele de intrare nu corespund restricțiilor impuse.")
Explicație rezolvare
Soluția calculează numărul minim de numere dintr-o listă care au ca factori primi doar numerele a și b date. Algoritmul descompune fiecare număr în factori primi, numără factorii primi egali cu p și q și returnează minimul dintre cele două valori. În plus, soluția include o funcție de validare a datelor de intrare.