Cerința

Se dă un şir format din n numere naturale, a1, a2, …, an. O pereche ( ai, aj), unde i<j, se numeşte eratostenică dacă i divide pe j şi ai divide pe aj. Determinaţi câte perechi eratostenice conţine şirul dat.

Date de intrare

Fișierul de intrare eratostene6.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire eratostene6.out va conține pe prima linie numărul perechilor eratostenice din şirul dat.

Restricții și precizări

• 2 ≤ n ≤ 100.000
• 0 ≤ a1, a2, …, an ≤ 1.000

Exemplu

eratostene6.in

4
2 3 0 6

eratostene6.out

3

Explicație

Cele 3 perechi eratostenice sunt: (2,0), (2,6), (3,6).

#include <bits/stdc++.h>
using namespace std;

ifstream cin("eratostene6.in");
ofstream cout("eratostene6.out");

int a[100001];

int main(){
    int n, cnt = 0;
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    for(int i = 1; i <= n / 2; ++i)
        for(int j = 2 * i; j <= n; j+=i)
            if(a[i] != 0 && a[j] % a[i] == 0)
                cnt++;
            else if(a[i] == 0 && a[j] == 0)
                cnt++;
    cout << cnt;
    return 0;
}