SUBSETS : Editorial

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";
}

}