4105 - NumarareDiv

Cerinţa

Se dă un vector cu n numere naturale. Să se determine câte dintre perechile de elemente din vector au același număr de divizori.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spaţii, reprezentând elementele vectorului.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou afișează pe ecran numărul c, reprezentând valoarea cerută. În caz contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

1 ⩽ n ⩽ 1000
elementele vectorului vor fi cuprinse între 1 și 1.000.000.000

Exemple

Exemplul 1

Intrare: 6; 13 3 8 7 9 25
Ieșire: Datele sunt introduse corect.; 4

Explicație exemplul 1

Perechile de elemente cu același număr de divizori sunt:
13 3 – cu câte 2 divizori fiecare
13 7 – cu câte 2 divizori fiecare
3 7 – cu câte 2 divizori fiecare
9 25 – cu câte 3 divizori fiecare

Exemplul 2

Intrare: 5; 10 2 -3 4 5
Ieșire: Datele nu corespund restricțiilor impuse.

Rezolvare

4105

def numar_divizori(n):

   divizori = 0
   for i in range(1, int(n ** 0.5) + 1):
       if n % i == 0:
           divizori += 1
           if i * i != n:
               divizori += 1
   return divizori

def cate_perechi_cu_acelasi_nr_divizori(vector, n):

   s = [numar_divizori(x) for x in vector]
   c = 0
   for i in range(n):
       for j in range(i+1, n):
           if s[i] == s[j]:
               c += 1
   print(c)

def citire_conform_restrictiilor(vector, n):

   if n < 1 or n > 1000:
       print("Datele nu corespund restricțiilor impuse.")
       exit()
   for x in vector:
       if x < 1 or x > 1000000000:
           print("Datele nu corespund restricțiilor impuse.")
           exit()
   if n != len(vector):
       print("Datele nu corespund restricțiilor impuse.")
       exit()
   print("Datele sunt introduse corect.")

if __name__ == '__main__':

   n = int(input())
   vector = list(map(int, input().split()))
   citire_conform_restrictiilor(vector, n)
   cate_perechi_cu_acelasi_nr_divizori(vector, n)

</syntaxhighlight>

Explicație rezolvare

Funcția numar_divizori(n) primește un număr întreg n ca argument și returnează numărul de divizori ai acestuia. Pentru a determina acest număr, se utilizează o buclă for care parcurge toate valorile între 1 și rădăcina pătrată a lui n și se verifică dacă n este divizibil cu aceste valori folosind operatorul modulo (%). Dacă n este divizibil cu un anumit număr, atunci se incrementează un contor numit divizori. De asemenea, se adaugă încă un divizor pentru fiecare valoare găsită, cu excepția cazului în care valoarea găsită este chiar rădăcina pătrată a lui n, pentru a evita dublarea divizorului. La final, funcția returnează numărul total de divizori.
Funcția cate_perechi_cu_acelasi_nr_divizori(vector, n) primește un vector de numere întregi vector și un număr întreg n reprezentând lungimea vectorului. Scopul acestei funcții este să numere câte perechi de numere din vector au același număr de divizori. Se folosește o buclă for dublă pentru a compara fiecare pereche posibilă de numere din vector. Dacă numărul de divizori al celor două numere este același, se incrementează un contor numit c. La final, se afișează valoarea contorului.
Funcția citire_conform_restrictiilor(vector, n) primește un vector „vector” și un număr întreg n reprezentând lungimea vectorului și verifică dacă vectorul și lungimea acestuia respectă restricțiile problemei. Restricțiile impuse sunt: n trebuie să fie între 1 și 1000, fiecare element al vectorului trebuie să fie între 1 și 1000000000, iar lungimea vectorului trebuie să fie egală cu n. Dacă una dintre aceste restricții nu este respectată, se afișează „Datele nu corespund restricțiilor impuse.” și programul se încheie folosind funcția exit(). Dacă toate restricțiile sunt respectate, se afișează „Datele sunt introduse corect.”.
La final, în blocul if __name__ == '__main__':, programul citește de la intrare un număr n, apoi un vector „vector”, și apoi apelează funcțiile citire_conform_restrictiilor(vector, n) și cate_perechi_cu_acelasi_nr_divizori(vector, n) pentru a rezolva problema dată.