Tekijät

input/code.cpp: In function 'int main()':
input/code.cpp:73:19: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
     scanf("%d", &N);
                 ~~^
input/code.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
input/code.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &A);
  ~~~~~^~~~~~~~~~~~

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAX = 2000000;
signed min_factor[MAX+1];
vector<int>prime;
void make_prime() {
    for (int i=2; i*i<=MAX; i++) {
	if (!min_factor[i]) {
	    min_factor[i] = i;
	    for (int j=i*i; j<=MAX; j+=i)
		if (!min_factor[j]) min_factor[j] = i;
	}
    }
    for (int i=2; i<=MAX; i++) {
	if (min_factor[i]==0) min_factor[i] = i;
	if (min_factor[i]==i) prime.push_back(i);
    }
}

int squarefree(int x) {
    int r = 1;
    for (int i=0; (int)prime[i]*prime[i] <= x; i++)  {
	if (x % prime[i] == 0) {
	    r *= prime[i];
	    while (x % prime[i] == 0) x /= prime[i];
	}
    }
    if (x != 1) r *= x;
    return r;
}

vector<int>fast_prime_factor(int n) { // n<=MAX
    vector<int>r;
    while (n>1) {
	int t=min_factor[n];
	r.push_back(t);
	while (n%t==0) n/=t;
    }
    return r;
}

const int MAX_A = 1000000;
int nC2(int n) { return (int)n * (n-1) / 2; }
int nC3(int n) { return (int)n * (n-1) * (n-2) / 6; }

int D[MAX_A + 11], mu[MAX_A + 11];
int N;

void rec(int cnt, const vector<int>&f, const int val) {
    if (cnt == (int)f.size()) {
	D[val]++;
	return;
    }

    rec(cnt+1, f, val);
    rec(cnt+1, f, val*f[cnt]);
}


signed main() {
    make_prime();

    for (int i=1; i<=MAX_A; i++) mu[i] = 1;
    for (int i=0; prime[i] <= MAX_A; i++) {
	for (int j=prime[i]; j<=MAX_A; j+=prime[i])
	    mu[j] *= -1;
	for (int j=(int)prime[i]*prime[i]; j<=MAX_A; j+=(int)prime[i]*prime[i])
	    mu[j] = 0;
    }

    scanf("%d", &N);
    for (int i=0; i<N; i++) {
	int A;
	scanf("%lld", &A);

	vector<int> f = fast_prime_factor(A);
	rec(0, f, 1);
    }

    int ans = 0;
    for (int i=1; i<=MAX_A; i++) {
	ans += mu[i] * nC2(D[i]);
	//ans += mu[i] * nC3(D[i]);
    }

    printf("%lld\n", ans);
    return 0;
}

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