XOR Hashing

#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
const long long N = 1e6, mod = 999999999989;
int c[N + 1], a[41], n;
bool b[N + 1];
vector<long long> Cnt1, Cnt2;
void Sieve()
{
    fill(b + 1, b + N + 1, true);
    for (int i = 2; i * i <= N; ++ i)
    {
        if (b[i])
        {
            for (int j = i * i; j <= N; j += i)
            {
                if (b[j])
                {
                    b[j] = false;
                    c[j] = i;
                }
            }
        }
    }
    for (int i = 2; i <= N; ++ i)
    {
        if (b[i])
        {
            c[i] = i;
        }
    }
}
void Gen(int i, int lim, vector<long long>& Cnt, long long Carry)
{
    if (i == lim + 1)
    {
        Cnt.push_back(Carry);
        return ;
    }
    Gen(i + 1, lim, Cnt, Carry);
    long long bruh = __gcd(Carry, (long long)a[i]);
    Carry /= bruh;
    Carry *= a[i]/bruh;
    Carry %= mod;
    Gen(i + 1, lim, Cnt, Carry);
}
void read()
{
   cin >> n;
   for (int i = 1; i <= n; ++ i)
   {
       cin >> a[i];
       int res = 1;
       while (a[i] > 1)
       {
           int tmp = c[a[i]];
           int cnt = 0;
           while (a[i] % tmp == 0)
           {
               cnt = (cnt + 1) % 2;
               a[i] /= tmp;
           }
           res *= ((cnt == 0) ? 1 : tmp);
       }
       a[i] = res;
   }
   Gen(1, n/2, Cnt1, 1);
   Gen(n/2 + 1, n, Cnt2, 1);
}
void solve()
{
   long long res = 0;
   sort(Cnt2.begin(), Cnt2.end());
   for (long long i : Cnt1)
   {
       res += (long long)(upper_bound(Cnt2.begin(), Cnt2.end(), i) - lower_bound(Cnt2.begin(), Cnt2.end(), i));
   }
   cout << res - 1;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen(TASK".INP", "r", stdin);
    //freopen(TASK".OUT", "w", stdout);
    Sieve();
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        cerr << "Case " << __ << ": ";
        read();
        solve();
    }
}