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

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.