Cod sursa(job #2677099)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 25 noiembrie 2020 19:56:49
Problema Pairs Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
 
#define fisier 1
 
using namespace std;
 
typedef long long ll;
 
const int mod = 1000000007;
const double dancila = 3.14159265359; // PI 
const double eps = 1e-9;
 
int n, val;
bool fr[1000002];

int prim[1000002];

ll ans;
 
 
int main()
{
	#ifdef fisier
		ifstream cin("pairs.in");
		ofstream cout("pairs.out");
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	for(int i = 1; i <= n; ++i)
	{
		cin >> val;
		fr[val]++;
	}
	
	for(int i = 2; i <= 1000000; ++i)
	{
		bool ad = 0;
		if(!prim[i])
			ad = 1;
		int cnt = 0;
		for(int j = i; j <= 1000000; j += i)
		{
			prim[j] += ad;
			cnt += fr[j];
		}
		if(ad)
		{
			if(prim[i] % 2 == 1)
				ans += (1LL * (cnt - 1) * cnt) / 2;
			else
				ans -= (1LL * (cnt - 1) * cnt) / 2;
		}
	}
	
	cout << 1LL * n * (n-1) / 2 - ans;
	return 0;
}