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