Tekijät

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define F first
#define S second

using namespace std;

const int N=1e6;
vector<int> fact[N+1];
ll cnt[N+1];

void incr(int k, int ind, int cur) {
	if (ind==(int)fact[k].size()) {
		cnt[cur]++;
		return;
	}
	incr(k,ind+1,cur);
	incr(k,ind+1,cur*fact[k][ind]);
}

ll get(int k, int ind, int cur) {
	if (ind==(int)fact[k].size()) return cnt[cur];
	return get(k,ind+1,cur)-get(k,ind+1,cur*fact[k][ind]);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	for (int k=2;k<=N;k++) {
		if (fact[k].size()==0) {
			for (int j=1;j*k<=N;j++) fact[j*k].push_back(k);
		}
	}
	int n;
	cin>>n;
	ll res=0;
	for (int i=0;i<n;i++) {
		int x;
		cin>>x;
		res+=get(x,0,1);
		incr(x,0,1);
	}
	cout<<res<<"\n";
}

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