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 1

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 1

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

<syntaxhighlight lang="python" line="1">

1. 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)

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

def main():

   """
   Funcția principală
   """
   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)
       print("Datele sunt introduse corect.")

       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)

main()

</syntaxhighlight>