Tekijät

#include <bits/stdc++.h>

typedef long long ll;

#define M 1000000007

using namespace std;

set<int> factors(int n) {
    set<int> r;
    if (n == 1) {
        r.insert(1);
        return r;
    }

    int div = 2;
    while (n > 1) {
        if (div * div > n) {
            r.insert(n);
            break;
        }

        if (n % div == 0) {
            r.insert(div);
            n /= div;
            div = 1;
        } 
        div++;
    }
    return r;
} 

bool ok(set<int> s1, set<int> s2) {
    for (int x : s1) {
        if (s2.find(x) != s2.end()) return false;
    }
    return true;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
    cin >> n;

    vector<int> v(n);

    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }

    vector<set<int>> ft;

    for (int i = 0; i < n; ++i) {
        ft.push_back(factors(v[i]));
    }

    ll ans = 0;

    for (int i = 0; i < n; ++i) {
        ll s = 0;
        //cout << "i: " << i << endl;
        for (int j = i+1; j < n; ++j) {
            if (i == j) continue;
            if (ok(ft[i], ft[j])) {
                s++;
                //cout << "\t" << j << endl;
            }
        }
        ans += s;
    }

    cout << ans << endl;

	return 0;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 5

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 3

Verdict: TIME LIMIT EXCEEDED