Tekijät

#include <iostream>
#include <vector>
#include <map>
//#include "stdlib_printing.hh"

typedef int32_t LL;
using namespace std;

int main(){
    LL n; cin >> n;
    vector<LL> v(n);
    map<LL,LL> vcounts;
    LL xmax = 0;
    for(LL i = 0; i < n; i++){
        cin >> v[i];
        xmax = max(xmax, v[i]);
        vcounts[v[i]]++;
    }

    vector<bool> isprime(xmax+1,true); isprime[0] = false; isprime[1] = false;
    vector<vector<LL> > PD(xmax+1); // C[i] = Distinct prime divisors of i
//    vector<vector<LL> > D(xmax+1); // D[i] = Divisors of i
    vector<LL> C(xmax+1); // C[i] = Number of items in the input that are divisible by i

    for(LL d = 2; d <= xmax; d++){
        for(LL k = 1; d*k <= xmax; k++){
//            D[d*k].push_back(d);
            if(isprime[d]) PD[d*k].push_back(d);
            if(k > 1) isprime[k*d] = false;
            C[d] += vcounts[d*k];
        }
    }
/*
    for(LL x : v){
        for(LL d : D[x]) C[d]++;
    }*/

    long long ans = 0;
    for(LL x : v){
        if(x == 1){
            ans += n-1;
            continue;
        }
        LL m = PD[x].size();
        LL howmany = 0;
        for(LL mask = 1; mask < (1LL << m); mask++){
            LL ones = __builtin_popcount(mask);
            LL sign = ones % 2 == 1 ? 1 : -1;
            LL d = 1;
            for(LL i = 0; i < m; i++){
                if(mask & (1LL << i)) d *= PD[x][i];
            }
            howmany += sign * C[d];
        }
        ans += n - howmany;
    }

    cout << ans/2 << endl; // Divide by two because we report unordered pairs

    //cout << isprime << endl;
    //cout << PD << endl;
    //cout << D << endl;
    //cout << C << endl;


}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 2, 3

Verdict: ACCEPTED

Test 4

Group: 3

Verdict: ACCEPTED

Test 5

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 3

Verdict: TIME LIMIT EXCEEDED