Tekijät

#include <bits/stdc++.h>
 
#define N 1000001
int p[N], dp[N];
long jaettavia[N];
 
int main() {
	int n;
	dp[1] = 1;
	for (int i = 2; i < N; ++i) {
		if (!p[i]) for (int j = i; j < N; j += i) {
			if (!p[j]) {
				p[j] = i;
			}
		}
		if (p[i / p[i]] == p[i]) {
			dp[i] = 0;
		} else {
			dp[i] = -1 * dp[i / p[i]];
		}
	}
	std::cin >> n;
	std::vector<int> luvut(n);
	for (int i = 0; i < n; ++i) {
		std::cin >> luvut[i];
		int l = luvut[i];
		for (int j = (int)sqrt(l); j; j--) {
			if (l % j == 0) {
				jaettavia[j] += 1;
				if (j*j != l) {
					jaettavia[l/j] += 1;
				}
			}
		}
	}
	long tulos = 0;
	for (int x = 1; x <= 1000000; ++x) {
		tulos += dp[x] * (jaettavia[x] * (jaettavia[x] - 1) / 2);
	}
	std::cout << tulos << std::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