Tekijät

#include <iostream>
using namespace std;
const int MN = 1<<17;
const int MX = 1<<20;
int xs[MN];
int ps[MX];
bool nonp[MX];

int counts[MX];
int fs[32];

int go(int x, int f, int c) {
	if (f<0) return counts[x]++ * c;
	return go(x, f-1, c) + go(x*fs[f], f-1, -c);
}

int main() {
	int P=0;
	for(int i=2; i<MX; ++i) if (!nonp[i]) {
		ps[P++] = i;
		for(int j=2*i; j<MX; j+=i) nonp[j]=1;
	}
	int n;cin>>n;
	long long res=0;
	while(n--) {
		int x;cin>>x;
		int f=0;
		for(int i=0; x>1; ++i) {
			int p = ps[i];
			if (x%p==0) {
				do x/=p; while(x%p==0);
				fs[f++] = p;
			} else if (p*p>x) break;
		}
		if (x>1) fs[f++] = x;
		res += go(1, f-1, 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