Cod sursa(job #2693487)

Utilizator gasparrobert95Gaspar Robert Andrei gasparrobert95 Data 6 ianuarie 2021 10:30:57
Problema Pairs Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <bits/stdc++.h>
#define ll long long
#define LMAX 1000005
using namespace std;
ifstream fin("pairs.in");
ofstream fout("pairs.out");
bool exista[LMAX], viz[LMAX];
int n, el, maxim, nr_prime[LMAX];
ll ans;

int main() {
    fin >> n;
    for (int i = 1; i <= n; ++i) {
        fin >> el;
        exista[el] = true;
        maxim = max(maxim, el);
    }
    for (int i = 2; i <= maxim; ++i) {
        if (viz[i])
            continue;
        ll cnt = 0;
        for (int j = i; j <= maxim; j += i) {
            if (nr_prime[i] == 0) {
                ++nr_prime[j];
                if (j % (i * i) == 0)
                    viz[j] = true;
            }
            cnt += exista[j];
        }
        if (nr_prime[i] % 2 == 1)
            ans += cnt * (cnt - 1) / 2;
        else
            ans -= cnt * (cnt - 1) / 2;
    }
    fout << (ll)n * (n - 1) / 2 - ans;
    return 0;
}