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;
}
You create vector $$$res$$$ of size $$$n$$$ on each call of $$$upf$$$, so your complexity is $$$n\times\sum A_i$$$