Rezolvare PBinfo #4507

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).