A6.细胞分裂 超AC题解

📌 一、程序整体结构回顾
程序的大致逻辑如下：

读取输入：

n：细胞种类数
m1, m2：表示试管总数 $ M = m_1^{m_2} $
s[i]：每种细胞的分裂倍数
质因数分解 $ m_1 $：

使用埃氏筛法预处理质数，然后对 m1 进行质因数分解
每个质因数的指数乘以 m2，得到最终的质因数幂次
对每种细胞判断其是否能分裂成满足条件的数量：

检查每个质因数是否在 s[i] 中出现
若出现，计算需要多少次分裂才能满足该质因数的指数要求
取所有质因数中所需分裂次数的最大值作为该细胞的最小 最终取所有细胞中时间最小的那个，若都不能满足则输出 -1
📌 二、逐部分时间复杂度分析
✅ 1. 质因数分解部分（筛法 + 分解 m1）
for (i = 2; i <= xx; i++)
{
if (p[i])
{
if (m1 % i == 0)
{
prime[size][1] = i;
prime[size][2] = 1;
}
}
int tim = 2;
while (tim * i <= m1)
{
p[tim * i] = 0;
tim;
}
}
xx = floor(sqrt(m1))，最多到 $ \sqrt{m_1} $
内部的 while 是筛法标记合数，总共运行 $ O(m_1 \log \log m_1) $ 次（标准筛法复杂度）
筛法时间复杂度：$ O(m_1 \log \log m_1) $
✅ 2. 质因数指数统计部分
for (i = 1; i <= size; i++)
{
int num = prime[i][1];
while (m1 % (num * prime[i][1]) == 0)
{
num *= prime[i][1];
prime[i][2];
}
prime[i][2] *= m2;
}
每个质因数最多分解到 $ m_1 $ 的幂次，最多循环 $ \log_{p_i}(m_1) $ 次
总共最多 $ O(\log m_1) $ 个质因数
所以这部分时间复杂度为：$ O(\log m_1 \cdot \log m_1) = O((\log m_1)^2) $
✅ 3. 对每种细胞进行判断
for (i = 1; i <= n; i)
{
for (j = 1; j <= size; j++)
{
if (s[i] % prime[j][1] != 0) break;

    int tim = 1;
    long long num = prime[j][1];
    while (s[i] % (num * prime[j][1]) == 0)
    {
        num *= prime[j][1];
        tim++;
    }
    int an = (prime[j][2]-1) / tim + 1;
    if (an > f[i]) f[i] = an;
}

}
外层循环：n 次（最多 10000）
内层循环：size 次（最多 $ O(\log m_1) $）
while 循环最多执行 $ \log_{p}(s_i) $ 次，即 $ O(\log s_i) $
因此，这部分时间复杂度为：

$ O(n \cdot \log m_1 \cdot \log s_i) $

其中：

n 最多为 10000
log m1 最多为 $ \log(3 \times 10^4) \approx 15 $
log s_i 最多为 $ \log(2 \times 10^9) \approx 30 $
所以这部分复杂度约为：

$ 10000 \times 15 \times 30 = 4500000 $，是可以接受的

📌 三、总时间复杂度总结
模块 时间复杂度
质因数筛法 $ O(m_1 \log \log m_1) $
质因数指数统计 $ O((\log m_1)^2) $
对每种细胞判断 $ O(n \cdot \log m_1 \cdot \log s_i) $
总时间复杂度：

O
(
m
1
log
⁡
log
⁡
m
1
+
n
⋅
log
⁡
m
1
⋅
log
⁡
s
i
)
O(m
1
​
loglogm
1
​
+n⋅logm
1
​
⋅logs
i
​
)

代码：

#include <bits/stdc++.h>
using namespace std;
int n,m1,m2,ans = 150000; 
int i,j;
int s[10001],f[10001];
bool p[30001];
int prime[501][3],size = 0;
int main(void)
{
    memset(p,1,sizeof(p));
    memset(f,0,sizeof(f));
    scanf("%d%d%d",&n,&m1,&m2);
    if (m1 == 1)
    {
        printf("0");
        return 0;
    } // If the number of tubes is 1, the conditions are met directly 若试管数为1，直接符合条件 
    for (i = 1; i <= n; i++)
      	scanf("%d",&s[i]);
    int xx = floor(sqrt(m1));
    for (i = 2; i <= xx; i++)
    {
        // Quality finding factor 找质因数 
      	if (p[i])
      	{
            if (m1 % i == 0)
            {
                prime[++size][1] = i;
                prime[size][2] = 1;
            }
        }
    	int tim = 2;
    	while (tim * i <= m1)
    	{
    		p[tim * i] = 0;
        	tim++;
         }
	}
    for (i = 1; i <= size; i++) // Number of quality finding factors 找质因数个数 
    {
        int num = prime[i][1];
        while (m1 % (num * prime[i][1]) == 0)
        {
            num *= prime[i][1];
            prime[i][2]++;
        }
        prime[i][2] *= m2;
    }
    if (size == 0) // If it is a prime number, the prime factor is itself 若为质数，质因数为本身 
    {
        prime[++size][1] = m1;
        prime[size][2] = m2;
    }
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= size; j++)
        {
            if (s[i] % prime[j][1] != 0) // If there is no certain factor, break directly 
            {
                f[i] = 150000; // Maximum: 10000 * log 2 30000
                break;
            }
            int tim = 1;
            long long num = prime[j][1];
            while (s[i] % (num * prime[j][1]) == 0)
            {
                num *= prime[j][1];
                tim++;
            }
            int an = (prime[j][2]-1) / tim + 1; // Equivalent to ceil function
            if (an > f[i]) f[i] = an;
        }
    }   
    for (i = 1; i <= n; i++)
      	if (ans > f[i]) ans=f[i];
    if (ans == 150000) printf("-1"); 
    else printf("%d",ans);
    return 0;
}