2241 - Inspectorat

Cerinţa

Se dau n perechi de numere naturale și pentru fiecare pereche (x,y) trebuie să se afle câte numere naturale nenule strict mai mici decât produsul x * y sunt prime cu x * y.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n perechi de numere naturale x și y.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran: "Datele sunt introduse corect.",programul va afișa pe ecran, pentru fiecare pereche (x, y) valoarea cerută, urmată de enter. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• 1 ≤ n ≤ 10 000
• Pentru fiecare pereche (x, y), 2 ≤ x, y ≤ 200 000
• Două numere sunt prime între ele dacă cel mai mare divizor al lor este 1.
• Atenție, produsul a două numere poate depăși valoarea maximă admisă de tipul int.
• Această ultimă precizare este disponibilă numai inspectorilor.

Exemple

Exemplul 1

ecran

Introduceți numărul de perechi: 3

Introduceți perechea 1: 3 4

Introduceți perechea 2: 3 3

Introduceți perechea 3: 97 33

ecran

Datele sunt introduse corect.

Numărul de numere nenule strict mai mici decât produsul 3 * 4 care sunt prime cu 3 * 4 este: 4

Numărul de numere nenule strict mai mici decât produsul 3 * 3 care sunt prime cu 3 * 3 este: 6

Numărul de numere nenule strict mai mici decât produsul 97 * 33 care sunt prime cu 97 * 33 este: 1920

Exemplul 2

ecran

Introduceți numărul de perechi: 2

Introduceți perechea 1: 3 7

Introduceți perechea 2: 10 12

ecran

Datele sunt introduse corect.

Numărul de numere nenule strict mai mici decât produsul 3 * 7 care sunt prime cu 3 * 7 este: 12

Numărul de numere nenule strict mai mici decât produsul 10 * 12 care sunt prime cu 10 * 12 este: 32

Exemplul 3

ecran

Introduceți numărul de perechi: 3

Introduceți perechea 1: 4 5

Introduceți perechea 2: 10.5 12

ecran

Datele nu corespund restricțiilor impuse.

Rezolvare

# 2241 - Inspectorat
import math


def valideaza_datele_intrare(n, perechi):
    """
    Verifică dacă datele de intrare sunt valide.

    Verifică dacă numărul de perechi este egal cu n și dacă toate numerele din perechi sunt întregi și pozitive.
    """
    if len(perechi) != n:
        print("Datele nu corespund restricțiilor impuse.")
        exit(0)

    for x, y in perechi:
        if not isinstance(x, int) or not isinstance(y, int) or x <= 1 or y <= 1 or x > 200000 or y > 200000:
            print("Datele nu corespund restricțiilor impuse.")
            exit(0)

    print("Datele sunt introduse corect.")


def calculeaza_numar_prime_cu_phi(n):
    """
    Calculează numărul de numere nenule strict mai mici decât produsul x * y care sunt prime cu x * y.
    """
    produs = n[0] * n[1]
    result = produs
    d = 2
    while d * d <= produs:
        if produs % d == 0:
            while produs % d == 0:
                produs //= d
            result = result // d * (d - 1)
        d += 1
    if produs > 1:
        result = result // produs * (produs - 1)
    return result


if __name__ == '__main__':
    try:
        n = int(input("Introduceți numărul de perechi: "))
        perechi = []
        for i in range(n):
            x, y = map(int, input(f"Introduceți perechea {i+1}: ").split())
            perechi.append((x, y))

        valideaza_datele_intrare(n, perechi)

        for pereche in perechi:
            count = calculeaza_numar_prime_cu_phi(pereche)
            print(f"Numărul de numere nenule strict mai mici decât produsul {pereche[0]} * {pereche[1]} care sunt prime cu {pereche[0]} * {pereche[1]} este: {count}")

    except ValueError:
        print("Datele nu corespund restricțiilor impuse.")
        exit(0)

Explciatie

Valideaza_datele_intrare(n, perechi): Verifică dacă datele de intrare sunt valide. Această funcție primește numărul de perechi n și o listă de perechi perechi, apoi verifică dacă numărul de perechi este egal cu n și dacă toate numerele din perechi sunt întregi și pozitive. Dacă datele nu sunt valide, afișează un mesaj corespunzător și încheie programul prin apelarea funcției exit(0). Dacă datele sunt valide, afișează un mesaj de confirmare.

Calculeaza_numar_prime_cu_phi(n): Calculează numărul de numere nenule strict mai mici decât produsul x * y care sunt prime cu x * y. Această funcție primește o pereche de numere n, apoi calculează produsul x * y al celor două numere și numărul de numere prime mai mici decât x * y care sunt prime cu x * y.

Main(): Aceasta este funcția principală care rulează întregul program. În această funcție, întâi citim numărul de perechi și apoi citim perechile de numere de la utilizator. Apoi, apelăm funcția valideaza_datele_intrare pentru a verifica dacă datele de intrare sunt valide. Dacă datele sunt valide, apelăm funcția calculeaza_numar_prime_cu_phi pentru fiecare pereche de numere citită și afișăm numărul de numere prime mai mici decât produsul x * y care sunt prime cu x * y. Dacă datele de intrare nu sunt valide, afișăm un mesaj corespunzător și încheiem programul prin apelarea funcției exit(0).