2306 - Numere 22

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

<syntaxhighlight lang="python" line> 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.")

</syntaxhighlight>

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.