0664 - Nr Perechi

Cerinţa

Gigel a învăţat la matematică despre cel mai mic multiplu comun a două numere şi acum trebuie să determine pentru fiecare valoare x dintr-un set de valori date câte perechi ordonate de numere naturale (a,b) au cel mai mic multiplu comun x.

Date de intrare

Programul citește de la tastatură număr numar, apoi numere valori x.

Date de ieşire

Programul va afișa pe ecran n valori, separate prin exact un spaţiu; fiecare valoare afișată reprezintă numărul de perechi care au cel mai mic multiplu comun egal cu valoarea x corespunzătoare.

Restricții și precizări

• numar ∈ Ν
• 1 ⩽ numar ⩽ 1.000
• 1 ⩽ x ⩽ 2.000.000.000

Exemplu

Intrare

2

12 4

Ieșire

Datele de intrare corespund restricțiilor impuse.

15 5

Explicație

Cele 15 perechi pentru care cel mai mic multiplu comun este 12 sunt: (1,12), (2,12), (3,4), (3,12), (4,3), (4,6), (4,12), (6,4), (6,12), (12,1), (12,2), (12,3), (12,4), (12,6), (12,12).

Rezolvare

<syntaxhighlight lang="python" line> def validare_date(numar, numere):

   flag = False
   if 0 <= int(numar) <= 1_000:
       flag = all(isinstance(x, int) and 1 <= x <= 1_000_000 for x in numere)
   return flag

def numar_perechi_cu_cmmmc_x(x):

   divizor = 2
   putere_divizor = 1
   while x > 1:
       if x % divizor == 0:
           exponent_divizor = 0
           while x % divizor == 0:
               exponent_divizor += 1
               x //= divizor
           putere_divizor *= 2 * exponent_divizor + 1
       else:
           divizor += 1
       if x > 1 and divizor * divizor > x:
           putere_divizor *= 3
           break
   return putere_divizor

if __name__ == '__main__':

   numar = int(input())
   numere = list(map(int, input().split()))
   if validare_date(numar, numere):
       print("\nDatele de intrare corespund restricțiilor impuse.\n")
       for x in numere:
           print(numar_perechi_cu_cmmmc_x(x), end=' ')
   else:
       print("Datele de intrare nu corespund restricțiilor impuse.")

</syntaxhighlight>