Tekijät

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const int H = 1e6;
int cou[H+1];
int mob[H+1];
 
vector<int> primes;
int div_ind[H+1];
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
 
	for (int i = 0; i <= H; ++i) div_ind[i] = -1;
 
	mob[1] = 1;
	for (int i = 2; i <= H; ++i) {
		if (div_ind[i] == -1) {
			div_ind[i] = primes.size();
			primes.push_back(i);
			mob[i] = -1;
		}
		for (int j = 0; j <= div_ind[i]; ++j) {
			ll t = (ll) i * primes[j];
			if (t > H) break;
 
			div_ind[t] = j;
			if (j < div_ind[i]) mob[t] = -mob[i];
			else mob[t] = 0;
		}
	}
 
	int n;
	cin >> n;
	
	// \sum_{d | n} \mu(d) = [n == 1]
	// \sum_{i = 1}^{H} \sum_{j = 1}^{H} [gcd(i, j) == 1] w_i w_j
	//	= \sum_{i = 1}^{H} \sum_{j = 1}^{H} \sum_{d | gcd(i, j)} \mu(d) w_i w_j
	//	= \sum_{d = 1}^{H} \mu d (\sum_{d | i} w_i) (\sum_{d | j} w_j)
 
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		++cou[x];
	}
	ll res = -cou[1];
 
	for (int i = 1; i <= H; ++i) {
		for (int j = 2*i; j <= H; j += i) {
			cou[i] += cou[j];
		}
	}
 
	// for (int v = 1; v <= 20; ++v) cout << cou[v] << ' '; cout << '\n';
	// for (int v = 1; v <= 20; ++v) cout << mob[v] << ' '; cout << '\n';
 
	for (int d = 1; d <= H; ++d) {
		res += mob[d] * (ll)cou[d] * cou[d];
	}
	cout << res / 2 << '\n';
}

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