CF1823C Strongly Composite

· · 题解

思路

我们可以思考一下什么样子的合数是强合数。

首先一个数可以表示为 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\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);
    }
}