Tekijät

input/code.cpp: In function 'long long int brute(std::vector<long long int>)':
input/code.cpp:102:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++) {
               ~^~~~~~~~~
input/code.cpp:103:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=i+1; j<v.size(); j++)
                  ~^~~~~~~~~

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define M 1000000007
 
using namespace std;

vector<ll> P;
int c = 0;
int prm[1010101];
ll ans = 0;

vector<ll> tek[1010101];

bool prime(ll x) {
	return !prm[x];
}

int z[1010101];
ll dd[1010101];
ll cnt[1010101];
vector<ll> dh;

void haku1(ll s, ll pr, ll d) {
	ll d2 = d;
	queue<ll> q;
	queue<ll> q2;
	q2.push(s);
	vector<pair<int,int>> dv;
	map<ll,ll> mp;
lol:
	d += d2;
	d2 = 0;
	q = q2;
	q2 = {};
	while(!q2.empty())
		q2.pop();
	while(!q.empty()) {
		s = q.front();
		q.pop();
		int qq = 0;
		for(auto u:mp) {
			if(u.first%s == 0)
			qq +=u.second;
		}
		ll lk = cnt[s]-qq;
		ans -= lk;
		cnt[s]++;
		assert(s>1);
		if(lk)
			mp[s]+=lk;
		for(auto u:tek[pr]) {
			if(u < s && s%u == 0) {
				if(z[s/u] == c) {
					continue;
				} else {
					z[s/u] = c;
				}
				q2.push(s/u);
			}
		}
	
	}
	if(!q2.empty()) {
		goto lol;
	}
}

int cntt = 0;
int mx = 0;
void pr(ll x) {
	ll sm = 1;
	if(x == 1)
		return;
	vector<ll> v;
	if(prime(x)) {
		sm = x;
	} else {
		while(x > 1) {
			ll lk = prm[x];
			if(lk == 0) {
			sm *= x;
			v.push_back(x);
				break;
			}
			if(v.size() == 0 || v[v.size()-1] != lk) {
			sm *= lk;
			v.push_back(lk);
			}
			x /= lk;
		}
	}
	tek[sm] = v;
	assert(sm>1);
	haku1(sm, sm, 0);
	//cnt[sm]++;
}


ll brute(vector<ll> v) {
	ll ret = 0;
	for(int i=0; i<v.size(); i++) {
		for(int j=i+1; j<v.size(); j++)
			if(__gcd(v[i], v[j]) == 1)
				ret++;
	}
	return ret;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio();
	prm[1] = 1;
	for(ll i=2; i<=1000000; i++) {
		if(!prm[i]) {
			P.push_back(i);
			for(ll j=2; j*i<=1e6; j++)
				if(!prm[i*j])
					prm[i*j] = i;
		}
	}
	ll n;
	cin >> n;
	ans = n*(n-1)/2;
	vector<ll> bv;
	for(int i=0; i<n; i++) {
		int x;
		cin >> x;
		bv.push_back(x);
		c = i+1;
		pr(x);
	}
	cnt[1] = 0;

	cout << ans << endl;
}

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: TIME LIMIT EXCEEDED

Test 7

Group: 3

Verdict: ACCEPTED