2319 - abc

Cerința

Se dau două numere naturale nenule a şi b, iar produsul lor îl notăm cu c. Aflaţi cel mai mare divizor propriu al lui A=2^c-1.

Date de intrare

Programul citește de la tastatură numerele a şi b, separate prin spațiu.

Date de ieșire

Programul va afișa pe ecran numărul D, reprezentând cel mai mare divizor propriu al lui A, alături de un mesaj de validare a datelor introduse ("Input valid" sau instrucțiuni pentru reintroducerea lui a sau b).

Restricții și precizări

• 2 ⩽ a ⩽ 20
• 2 ⩽ b ⩽ 10.000
• Un divizor propriu al lui A este diferit de 1 şi de A

Exemplu

Intrare

3 2

Ieșire

Input valid

21

Explicație

Avem c=6 şi A=26-1=63. Cel mai mare divizor propriu al lui A este 21.

Rezolvare

def validate_a(a):
    if not (2 <= a <= 20):
        raise ValueError("a trebuie să fie între 2 și 20")


def validate_b(b):
    if not (2 <= b <= 10000):
        raise ValueError("b trebuie să fie între 2 și 10000")


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def largest_proper_divisor_of_A(a, b):
    validate_a(a)
    validate_b(b)
    print("Input valid")

    c = a * b
    A = 2 ** c - 1

    divisors = []
    for i in range(2, int(A ** 0.5) + 1):
        if A % i == 0:
            divisors.append(i)
            if i != A // i:
                divisors.append(A // i)

    divisors.sort(reverse=True)

    for divisor in divisors:
        if gcd(A, divisor) == divisor:
            return divisor

    raise ValueError("Nu există divizori proprii pentru A")


def main():
    a, b = map(int, input("Introduceți a și b, separate prin spațiu: ").split())
    divisor = largest_proper_divisor_of_A(a, b)
    print(f"Cel mai mare divizor propriu al lui A este: {divisor}")


if __name__ == "__main__":
    main()

Explicație cod

Acest cod definește patru funcții: validate_a(a), validate_b(b), gcd(a, b) și largest_proper_divisor_of_A(a, b), și apoi apelează funcția main() dacă script-ul este rulat ca program principal.

Funcția validate_a(a) verifică dacă argumentul a este un număr între 2 și 20. Dacă nu, generează o excepție de tip ValueError.

Funcția validate_b(b) verifică dacă argumentul b este un număr între 2 și 10000. Dacă nu, generează o excepție de tip ValueError.

Funcția gcd(a, b) calculează cel mai mare divizor comun (gcd) al lui a și b folosind algoritmul Euclid.

Funcția largest_proper_divisor_of_A(a, b) primește doi argumente a și b, validează valorile lor cu ajutorul funcțiilor validate_a(a) și validate_b(b) și scrie un mesaj de confirmare a validării datelor introduse, calculează c = a * b și A = 2 ** c - 1, și apoi găsește cel mai mare divizor propriu al lui A. Un divizor propriu al unui număr este un divizor strict mai mic decât acel număr. Dacă nu există niciun divizor propriu al lui A, funcția generează o excepție de tip ValueError.

Funcția main() citește de la tastatură două numere întregi separate prin spațiu, apoi apelează funcția largest_proper_divisor_of_A(a, b) pentru a găsi cel mai mare divizor propriu al lui A și îl afișează.