0664 - Nr Perechi

From Bitnami MediaWiki
Revision as of 10:29, 11 April 2023 by Robert Manc (talk | contribs)

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>