Tekijät

#include <bits/stdc++.h>

#define N 1000001
int seula[N], mobius[N], jaettavia[N];

int main() {
	int n;
	mobius[1] = 1;
	for (int i = 2; i < N; ++i) {
		if (!seula[i]) for (int j = i; j < N; j += i) {
			if (!seula[j]) {
				seula[j] = i;
			}
		}
		if (seula[i / seula[i]] == seula[i]) {
			mobius[i] = 0;
		} else {
			mobius[i] = -1 * mobius[i / seula[i]];
		}
	}
	std::cin >> n;
	for (int i = 0; i < n; ++i) {
		int l;
		std::cin >> l;
		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 += mobius[x] * (jaettavia[x] * (jaettavia[x] - 1L) / 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