# SUBSETS : Editorial

https://www.codechef.com/CSPK2020

SUBSETS : Editorial
Author: CodeChef Public Repository
Tester: easy3279
Editorialist : chaitanya_44
Difficulty : medium
Problem:

A good number is a positive integer which is not divisible by the cube (third power) of any prime. For example, 2, 3, 25=5⋅5, 63=7⋅9 and 2057=11⋅11⋅17 are good numbers, but 8=2⋅2⋅2, 9317=7⋅11⋅11⋅11 and 2401=7⋅7⋅7⋅7 are not good numbers.

A pair of positive integers (x,y) is special if x⋅y is a good number. A set of positive integers is nice if each pair of different integers from this set is special. In particular, the empty set is nice.

You are given a set of integers {A1,A2,…,AN}. Find the number of nice subsets of this set.

Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N.
The second line contains N space-separated integers A1,A2,…,AN.
Output
For each test case, print a single line containing one integer — the number of nice subsets.

Constraints
1≤T≤10
1≤N≤40
1≤Ai≤108 for each valid i
A1,A2,…,AN are pairwise distinct

Solution:

CPP14

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vi = vector;
using vl = vector;
using vb = vector;
using vvi = vector;
using vvl = vector;
using vvb = vector;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define pb push_back
#define mp make_pair
#define eb emplace_back
#define fst first
#define snd second

#define all(x) x.begin(), x.end()
#define con(a, x) (a.find(x) != a.end())

#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

#ifdef LOCAL
#define var(x) " [" << #x ": " << (x) << "] "
template auto decl(c *x) -> decltype(cerr << *x);
template char decl(…);
struct perr {
~perr() { cerr << endl; }
template typename
std::enable_if<sizeof(decl(0)) != 1, perr&>::type operator<<(c x) { cerr << boolalpha << x; return * this; }
template typename
std::enable_if<sizeof(decl(0)) == 1, perr&>::type operator<<(c x) {
*this << “[”;
for (auto it = begin(x); it != end(x); ++it) {
if (it != begin(x)) *this << ", ";
*this << *it;
}
*this << “]”;
return *this;
}
template<class c, class d>
perr& operator<<(pair<c, d> x) { return *this << “(” << x.first << ", " << x.second << “)”; }
};
#endif

const int MAXN = 2e8;

int main() {
fastio;

``````int T = 1;
cin >> T;

while (T--) {
int n;
cin >> n;

vl a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}

if (n == 1) {
cout << "2\n";
continue;
}

auto getFacts = [&](ll a) -> vector<pii> {
vector<pii> facts;
for (ll d = 2; d * d <= a; d++) {
if (a % d == 0) {
facts.emplace_back(d, 0);
while (a % d == 0) {
a /= d;
facts.back().second++;
}
}
}
if (a > 1) {
facts.emplace_back(a, 1);
a = 1;
}
return facts;
};

vector<vector<pii>> facts(n);
for (int i = 0; i < n; i++) {
facts[i] = getFacts(a[i]);
}

auto canTakeBoth = [&](int i, int j) -> bool {
auto iFact = facts[i], jFact = facts[j];
map<int, int> tmp;
for (auto factCnt : iFact) {
auto fact = factCnt.first;
auto cnt = factCnt.second;
if (cnt >= 3) return false;
tmp[fact] = cnt;
}
for (auto factCnt : jFact) {
auto fact = factCnt.first;
auto cnt = factCnt.second;
if (cnt >= 3) return false;
if (cnt + tmp[fact] >= 3) {
return false;
}
}
return true;
};

int leftHalf = n/2;
int rightHalf = n - leftHalf;

vvb g(n, vb(n, true));
vi leftNeis(leftHalf);

for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (!canTakeBoth(i, j)) {
g[i][j] = false;
g[j][i] = false;
}
else {
if (i < leftHalf and j >= leftHalf) {
leftNeis[i] |= (1 << (j - leftHalf));
}
}
}
}

auto getCntCliques = [&](int len, int offset) -> vi {
vi cntCliques((1 << len), 0);
int firstSetBit = 0;
for (int bit = len - 1; bit >= 0; bit--) {
if (mask & (1 << bit)) {
if (cntCliques[mask ^ (1 << bit)] == 0) {
}
else {
bool isClique = true;
for (int b2 = bit - 1; b2 >= 0; b2--) {
if (mask & (1 << b2)) {
if (g[offset + bit][offset + b2] == false) {
isClique = false;
break;
}
}
}
cntCliques[mask] = isClique ? 1 : 0;
}
break;
}
}
}
if (offset == 0) {
for (int bit = 0; bit < len; bit++) {
if (mask & (1 << bit)) {
}
}
}
}
return cntCliques;
};

vi cntLeftCliques = getCntCliques(leftHalf, 0);
vi cntRightCliques = getCntCliques(rightHalf, leftHalf);

ll cntTotalCliques = 0;