Cod sursa(job #2949145)

Utilizator rares89_Dumitriu Rares rares89_ Data 29 noiembrie 2022 23:20:31
Problema Pairs Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>

using namespace std;

ifstream fin("pairs.in");
ofstream fout("pairs.out");

int n, x, maxim, nrP[1000005], fr[1000005];
long long int ans;
bool c[1000005];
// nrp - nr divizori primi

int main() {
    fin >> n;
    for(int i = 1; i <= n; i++) {
        fin >> x;
        fr[x]++;
        maxim = max(maxim, x);
    }
    for(int i = 2; i <= maxim; i++) {
        if(!c[i]) {
            bool prim = !nrP[i];
            long long int cnt = 0;
            for(int j = i; j <= maxim; j += i) {
                if(prim) {
                    nrP[j]++;
                    if(j % (i * i) == 0) {
                        c[j] = true;
                    }
                }
                cnt += fr[j];
            }
            // comb(cnt, 2) 
            if(nrP[i] % 2 == 1) {
                ans += 1LL * cnt * (cnt - 1) / 2;
            } else {
                ans -= 1LL * cnt * (cnt - 1) / 2;
            }
        }
    }
    // comb(n, 2) - ans;
    fout << (1LL * n * (n - 1) / 2LL - ans);
    return 0;
}