📌 一、程序整体结构回顾
程序的大致逻辑如下：
读取输入：
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;
}
外层循环：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
)
代码：
