Tekijät

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
void testCase() {           
    
}
 
 
int sieve[2000001];
ll x[1000000];
ll occ[1000001];
bool seen[1000001];
vector<int> divisors[1100001];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    /*
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        testCase();
    }
    */
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> x[i];
    for (int i = 0; i < n; i++) seen[x[i]] = true;
    for (int i = 2; i <= 1100000; i++) {
        divisors[i].push_back(i);
        for (int j = 2*i; j <= 1100000; j += i) {
            if (!sieve[i]) sieve[j] = i;
            if (seen[j]) divisors[j].push_back(i);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int a : divisors[x[i]]) occ[a]++;
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        if (x[i] == 1) {
            continue;
        }
        vector<int> pf;
        while (sieve[x[i]]) {
            int a = sieve[x[i]];
            pf.push_back(a);
            while (x[i] % a == 0) x[i] /= a;
        }
        if (x[i] > 1) pf.push_back(x[i]);
        int k = pf.size();
        for (int ii = 1; ii < (1<<k); ii++) {
            int product = 1;
            for (int j = 0; j < k; j++) {
                if (ii & (1<<j)) {
                    product *= pf[j];
                }
            }
            if (__builtin_popcount(ii)%2 == 1) {
                ans += occ[product]-1;
            }
            else {
                ans -= occ[product]-1;
            }
        }
    }
    ans /= 2;
    cout << (ll)n*(n-1)/2 - ans << 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: ACCEPTED

Test 6

Group: 3

Verdict: ACCEPTED

Test 7

Group: 3

Verdict: ACCEPTED