思路
我们可以思考一下什么样子的合数是强合数。
首先一个数可以表示为 \(p_1^{c_1}\times p_2^{c_2}\times \cdots \times p_x^{c_x}\)。
那么这个数的约数个数为 \(s=(c_1+1)\times (c_2+1)\times \cdots \times (c_x+1)\)。那么，我们可以根据 \(s\) 初步排除一部分强合数：
-
若 \(s=1\)，则原数是 \(1\)，不可能为强合数。
-
若 \(s=2\)，则原数是质数，不可能为强合数。
所以如果 \(s\le2\)，则该数不可能为强合数。
再令质数的个数为 \(x\)，则合数的个数为 \(s-x-1\)。
所以只要 \(x\le s-x-1\Rightarrow 2\times x\le s-1\)，这个数就是强合数。
若一个数是强合数，我们考虑给它乘以若干个互不相同且之前没出现过的质数，假设质数的数量为 \(k\)。
那么只要 \(2\times(x+k)\le s\times 2^k -1\) 乘以这些质数后就还是强合数。
即需要证明 \(2\times k\le s\times (2^k-1)\)。
因为原数是强合数，所以 \(s\ge 3\)。
易知，\(k=1\) 时，一定满足条件，因为左侧是线性增长，右侧是指数增长，所以后续右侧一定会越来越比左侧大。
所以强合数乘以若干个互不相同且不是原数的质因数的质数，无论乘以多少个，它还是强合数。
再思考，如果乘以了已经存在过的质数，那么质数因数不会变，合数因数会变多，所以还是强合数。
综合一下，就是强合数乘以任意正整数后还是强合数。
再来思考，至少存在几个质因数可以成为强合数。
首先是只有一种质因数，如果只有一个，那原数就是质数，不可能为强合数；如果超过一个，那就是上面的 \(s=2\) 的情况，是强合数。
然后是至少有几个不同的质因数，令有 \(x\) 个不同的质因数，那么共有 \(2^x\) 个因数，有 \(2^x-x-1\) 个合数因数。
如果原数是强合数，那么 \(x\le 2^x-x+1\) 即 \(2^x-2\times x-1\ge 0\)，发现当且仅当 \(x\ge 3\) 时，原数是强合数。
因为一个强合数乘以任意一个正整数后还是强合数，所以只要这个数有一个质因数的个数大于等于 \(2\) 或者有至少 \(3\) 个质因数时是强合数。
因为前一种所需的最少质因数比后一种所需的最少质因数还要少，所以我们尽量先多造前一种强合数，再造后一种强合数
现在给定了 \(a_i\) 就代表 \(\prod_{i}^n a_i\) 是定值，然后对其进行质因数分解。对于所有的质因数，令其个数为 \(cnt\)，如果 \(cnt>1\)，那么这些质因子可以造出 \(\lfloor \frac{cnt}2\rfloor\) 个强合数，如果 \(cnt\) 是奇数，那么就会剩下一个质因数。
剩下的质因数可以三个一对造强合数，剩下的质因数就随便乘给任意数即可。
AC code
#include<bits/stdc++.h>
using namespace std;
int shu[10000005],pri[10000005],minp[10000005],cnt;
int T,n,a,b[10000005],num,siz;
map<int,int>m;
inline void init()//提前线性筛预处理每个数的最小质因数
{
for(int i=2;i<=10000000;++i)
{
if(!shu[i]) pri[++cnt]=i,minp[i]=i;
for(int j=1;j<=cnt&&pri[j]*i<=10000000;++j)
{
minp[pri[j]*i]=pri[j],shu[pri[j]*i]=1;
if(i%pri[j]==0) break;
}
}
}
inline void calc(int x)//除以最小质因数，较为快速地分解质因数
{
while(minp[x]>1) ++m[minp[x]],x/=minp[x];
if(x>1) ++m[x];
}
int main()
{
init();
scanf("%d",&T);
while(T--)
{
scanf("%d",&n),m.clear(),cnt=siz=0;
for(int i=1;i<=n;++i) scanf("%d",&a),calc(a);//乘起来在质因数分解，和每个数质因数分解，再把相同质数的指数相加是等效的，并且乘起来会导致数太多，线性筛没法预处理那么多，还可能会爆unsigned long long导致没有类型可以存
for(auto i:m)//遍历所有的质因数
{
cnt+=i.second/2;
if(i.second%2) ++siz;//统计剩下的质因数个数
}
cnt+=siz/3;
printf("%d\n",cnt);
}
}