4110 - NumarareSD

Sursa: 4110 - NumarareSD

---

Cerinţa

Se dă un vector cu n numere naturale. Să se determine câte dintre perechile de elemente din vector au aceeași sumă a divizorilor.

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

10 3 6 17 9 11

Ieșire

Datele sunt introduse corect.

2

Explicație exemplul 1

Perechile de elemente cu aceeași sumă a divizorilor sunt:
10 17 – cu suma 18
6 11 – cu suma 12

Exemplul 2

Intrare

5

10 2 -3 4 5

Ieșire

Datele nu corespund restricțiilor impuse.

Rezolvare

# 4110

import math


def suma_divizorilor(n):
    sumdiv = 0
    for d in range(1, int(math.sqrt(n))+1):
        if n % d == 0:
            sumdiv += d
            if d != n // d:
                sumdiv += n // d
    return sumdiv


def cate_perechi_cu_aceeasi_suma_diviz(vector, n):
    s = [suma_divizorilor(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_aceeasi_suma_diviz(vector, n)

Explicație rezolvare

   Funcția suma_divizorilor(n) primește un număr întreg n ca argument și calculează suma divizorilor acestuia. Pentru a face acest lucru, se parcurge un interval de la 1 la radicalul pătrat din n (inclusiv), iar pentru fiecare divizor d al lui n, se adaugă la suma sumdiv valoarea lui d și valoarea lui n // d (dacă d nu este egal cu n // d).
   Funcția cate_perechi_cu_aceeasi_suma_diviz(vector, n) primește un vector de numere întregi vector și un număr întreg n reprezentând lungimea vectorului. Această funcție calculează numărul de perechi de indici distincte din vector (i, j), cu i < j, pentru care suma divizorilor elementelor de pe pozițiile i și j din vector este aceeași. Acest lucru se face prin calcularea sumelor divizorilor pentru fiecare element din vector utilizând funcția suma_divizorilor(n), și apoi compararea acestor sume pentru a identifica perechile cu aceeași sumă de divizori.
   Funcția citire_conform_restrictiilor(vector, n) primește un vector de numere vector și un număr n reprezentând lungimea vectorului. Această funcție verifică dacă valorile lui n și ale elementelor din vector respectă anumite restricții impuse (n trebuie să fie între 1 și 1000, iar elementele vectorului trebuie să fie între 1 și 1000000000, n trebuie să fie lungimea vectorului "vector"), și dacă aceste restricții nu sunt îndeplinite afișează "Datele nu corespund restricțiilor impuse." și încheie execuția programului cu ajutorul comenzii exit(), iar dacă ele sunt îndeplinite afișează "Datele sunt introduse corect." și se continuă programul.
   În blocul if __name__ == '__main__': se realizează citirea valorii lui n de la tastatură, citirea vectorului de numere întregi vector de la tastatură, apelul funcției citire_conform_restrictiilor(vector, n) pentru a verifica restricțiile impuse asupra datelor de intrare, și apelul funcției cate_perechi_cu_aceeasi_suma_diviz(vector, n) pentru a calcula și afișa numărul de perechi de indici cu aceeași sumă de divizori, număr ce reprezintă valoarea cerută în problemă.