Tekijät

#include <bits/stdc++.h>

int main() {
	int n, m = 0;
	long tulos = 0;
	std::cin >> n;
	std::vector<int> luvut(n);
	for (int i = 0; i < n; ++i) {
		std::cin >> luvut[i];
		m = std::max(m, luvut[i]);
	}
	if (m <= 100) {
		std::unordered_map<int, int> maara;
		for (int luku: luvut) {
			maara[luku] += 1;
		}
		tulos = maara[1] * (maara[1] - 1);
		for (auto a: maara) {
			for (auto b: maara) {
				if (a.first != b.first && std::gcd(a.first, b.first) == 1) {
					tulos += a.second * b.second;
				}
			}
		}
		tulos /= 2;
	} else {
		std::vector<int> luvut_maskilla[256];
		for (int luku: luvut) {
			int bitit = (
				+ (luku %  2 ? 0 : 0x01)
				+ (luku %  3 ? 0 : 0x02)
				+ (luku %  5 ? 0 : 0x04)
				+ (luku %  7 ? 0 : 0x08)
				+ (luku % 11 ? 0 : 0x10)
				+ (luku % 13 ? 0 : 0x20)
				+ (luku % 17 ? 0 : 0x40)
				+ (luku % 19 ? 0 : 0x80)
			);
			for (int b = 0; b < 256; ++b) {
				if (!(bitit & b)) {
					for (int j: luvut_maskilla[b]) {
						if (std::gcd(luku, j) == 1) {
							tulos += 1;
						}
					}
				}
			}
			luvut_maskilla[bitit].push_back(luku);
		}
	}
	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: TIME LIMIT EXCEEDED

Test 5

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 3

Verdict: ACCEPTED

Test 7

Group: 3

Verdict: TIME LIMIT EXCEEDED