Hustle_Loyalty_Respect's blog

By Hustle_Loyalty_Respect, history, 4 years ago, In English

The problem I am solving is E. Coprime (in At coder's Beginners contest)

https://atcoder.jp/contests/abc177/tasks/abc177_e

My submission that gives TLE

https://atcoder.jp/contests/abc177/submissions/18061844

The problem I am facing comes with identifying if the numbers are pairwise coprime.

I did exactly what the editorial said — There should be no prime number that divides 2 numbers in the input array otherwise their gcd won't be 1. So I found out unique numbers that are prime factors for every number in the array and then when I spot that there exists a prime number which is a factorizing 2 numbers I set the ispwc = false (is_pairwise_coprime). But I get TLE

My code:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll cnt[1000005];

ll gcd(ll a , ll b) {
	
	if(a < b) {
		return gcd(b, a);
	}
   	
   	if(b==0) 
   		return a;

   	return gcd(b, a % b);
}


vector<bool> is_prime;
vector<ll> siever;

vector<ll> upf(ll n) {

	assert(n != 0 && n != 1); 

	// return unique primes that factorize n
	
	// for n = 100, we return [2, 5]

	vector<ll> res(n + 1);
	vector<ll> uniqs;

	ll curr = n;

	do {

		if(res[siever[curr]] == 0){
			uniqs.push_back(siever[curr]);
		}
		res[siever[curr]]++;

		curr = curr/siever[curr];

		if(curr == siever[curr]) {

			if(is_prime[siever[curr]] && res[siever[curr]] == 0) {
				uniqs.push_back(siever[curr]);
				res[siever[curr]]++;
			}

			break;
		}

	} while(true);

	return uniqs;
}

void sieve(ll n) {
	
	is_prime.assign(n + 1, true);
	siever.assign(n + 1, 0);

	for(ll i = 0; i < n + 1; ++i) {
		siever[i] = i;
	}

	is_prime[0] = is_prime[1] = false;

	for(ll i = 2; i <= sqrt(n); ++i) {

		if(is_prime[i]) {

			for(ll j = i * i; j <= n; j += i) {
				siever[j] = i;
				is_prime[j] = false;
			}
			
		}
	}

}

int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(0);

	ll n;
	cin >> n;

	// accumulator for setwise gcd
	ll c = 0;

	sieve(1000001);

	// is pairwise coprime
	bool ispwc = true;

	for(ll i=0; i<n; ++i) {
		
		ll x;
		cin >> x;
		
		c = gcd(c, x);

		if(x != 1) {

			// for each unique prime factor of x
			for(ll _p: upf(x)) {

				// cout << _p << " ";

				if(cnt[_p] != 0) {
					ispwc = false;
				}
				
				cnt[_p]++;
			}

			// cout << "\n";

		} 
		
	}

	// is setwise coprime
	bool isswc = c == 1;

	if(ispwc) {
		cout << "pairwise coprime" << endl;
	} 
	else if(isswc) {
		cout << "setwise coprime" << endl;
	}
	else {
		cout << "not coprime" << endl;
	}

	return 0;
}
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You create vector $$$res$$$ of size $$$n$$$ on each call of $$$upf$$$, so your complexity is $$$n\times\sum A_i$$$