Link to the Contest:
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);
for (int mask = 0; mask < (1 << len); mask++) {
cntCliques[mask] = 1;
int firstSetBit = 0;
for (int bit = len - 1; bit >= 0; bit--) {
if (mask & (1 << bit)) {
if (cntCliques[mask ^ (1 << bit)] == 0) {
cntCliques[mask] = 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++) {
for (int mask = 0; mask < (1 << len); mask++) {
if (mask & (1 << bit)) {
cntCliques[mask] += cntCliques[mask ^ (1 << bit)];
}
}
}
}
return cntCliques;
};
vi cntLeftCliques = getCntCliques(leftHalf, 0);
vi cntRightCliques = getCntCliques(rightHalf, leftHalf);
ll cntTotalCliques = 0;
for (int rightMask = 0; rightMask < (1 << rightHalf); rightMask++) {
if (cntRightCliques[rightMask] == 0) continue;
int leftMask = 0;
for (int leftNode = 0; leftNode < leftHalf; leftNode++) {
if ((leftNeis[leftNode] & rightMask) == rightMask) {
leftMask |= (1 << leftNode);
}
}
cntTotalCliques += cntLeftCliques[leftMask];
}
cout << cntTotalCliques << "\n";
}
}