# PBinfo #4507 – Eratostene9 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Cerința
Se dă un șir A format din N numere naturale nenule. Aflați numărul perechilor de indici, (i,j), cu i≠j, pentru care A[i] divide pe A[j].

Date de intrare
Programul citește de la tastatură numărul N, iar apoi N numere naturale, separate prin spații, reprezentând elementele șirului A.

Date de ieșire
Programul va afișa pe ecran numărul cerut.

Restricții și precizări

1 ≤ N ≤ 100.000
cele N numere citite vor fi mai mici decât 1.000.000

Exemplul 1:
Intrare

5
1 4 3 2 5
Ieșire

5
Explicație
Perechile de indici (i,j), cu i≠j, pentru care A[i] divide pe A[j], sunt: (1,2), (1,3), (1,4), (1,5), (4,2).

Exemplul 2:
Intrare

4
2 3 2 4
Ieșire

4
Explicație
Perechile de indici (i,j), cu i≠j, pentru care A[i] divide pe A[j], sunt: (1,3), (3,1), (1,4), (3,4).

## Cod sursă C++

```cpp
#include <iostream>
using namespace std;
int n,i,a,j;
long long v[1000003], nr;
int main()
{
    cin >> n;
    for(i = 1; i <= n; i++)
    {
        cin >> a;
        v[a]++;
    }
    for(i = 1; i <= 1000000; i++)
    {
        nr += v[i]*(v[i]-1);
        j = i+i;
        while(j <= 1000000)
        {
            nr += v[i]*v[j];
            j = j+i;
        }
    }
    cout << nr;
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4507)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4507/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4507/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)