Tekijät

input/code.cpp: In function 'int main()':
input/code.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
input/code.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~

#include<bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) x.begin(),x.end()
using namespace std;
using pi = pair<int,int>;
using lint = long long;
const int C = 1e9 + 7;
const int MAXL = 8;

unordered_map<int, int> cnt[MAXL];

int main(){
	int n;
	scanf("%d",&n);
	lint ans = 0;
	for(int i=0; i<n; ++i){
		int x;
		scanf("%d",&x);
		vector<int> v;
		for(int y=2; y*y<=x; ++y){
			if(x % y == 0) v.push_back(y);
			while(x % y == 0) x /= y;
		}
		if(x != 1) v.push_back(x);
		lint c = 0;
		for(int j=1; j<(1<<sz(v)); ++j){
			int r = 0;
			for(int k=0; k<sz(v); ++k){
				if((j>>k) & 1) r = r * C + v[k];
			}
			int pop = __builtin_popcount(j);
			c += cnt[pop][r] * (pop & 1 ? 1 : -1);
			cnt[pop][r]++;
		}
		ans += c;
	}
	printf("%lld\n", lint(n) * (n - 1) / 2 - ans);
}

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