AC助手的题解（A6.细胞分裂）

🔍 一、题目回顾与核心思想
这个问题的本质是：

给定 $ M = m_1^{m_2} $，我们需要找到一种细胞（分裂因子为 $ S_i $），使得经过最少时间 $ t $ 后，细胞数量 $ S_i^t $ 能被 $ M $ 整除。

即：求最小的 $ t \geq 0 $，使得 $ M \mid S_i^t $，对所有 $ i $ 取最小值。

关键点：
不是模拟分裂过程，而是从质因数分解角度判断 $ S_i^t $ 是否包含足够的质因子以覆盖 $ M = m_1^{m_2} $。
如果某个质因子在 $ S_i $ 中不存在，则永远无法满足条件。
对每个质因子 $ p $，设其在 $ M $ 中的指数为 $ e $，在 $ S_i $ 中的指数为 $ a $，则需要最小的 $ t $ 满足 $ a \cdot t \geq e $ → $ t \geq \lceil e / a \rceil $
🧠 二、你的代码逻辑梳理
我们逐段解析关键操作：

int n, m1, m2, ans = 150000;
int s[10001], f[10001];
bool p[30001]; // 筛法用的素数标记数组
int prime[501][3], size = 0; // 存储 m1 的质因数及其总指数（乘上 m2）
步骤 1：特判 $ m1 == 1 $if (m1 == 1) { printf("0"); return 0; } ✅ 时间：$ O(1) $

步骤 2：埃拉托斯特尼筛法预处理 + 分解 $ m1 $ 的质因数
memset(p, 1, sizeof(p));
int xx = floor(sqrt(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;
}
}
}
⚠️ 注意：这里的写法 不是标准筛法，存在冗余！

问题分析：
外层循环是 $ i = 2 $ 到 $ \sqrt{m_1} $
内部 while 实现的是“把 i 的倍数标记为合数”，但它是放在 if (p[i]) 里面的 —— 这其实类似于埃氏筛的思想。
但是这个内层 while 是从 tim=2 开始，每次做 tim++，等价于遍历 2i, 3i, ..., k*i <= m1，即标准筛法中的标记步骤。
但注意：这不是先筛整个表再分解，而是在试除的同时进行筛标记。虽然能工作，但效率不如先筛素数表或直接试除更优。

时间复杂度估算：
外层循环：$ O(\sqrt{m_1}) $
内层 while：对每个素数 $ i $，执行约 $ \frac{m_1}{i} $ 次？不对！实际上只是标记倍数，总共会标记 $ O(m_1 \log \log m_1) $ 次？不完全是，因为只处理到 $ \sqrt{m_1} $
但实际上，由于只处理 $ i \le \sqrt{m_1} $，且每个 $ i $ 标记其倍数直到 $ m_1 $，所以这部分总的运行时间接近：

$ \sum_{i=2}^{\sqrt{m_1}} \frac{m_1}{i} \approx m_1 \ln \sqrt{m_1} = O(m_1 \log m_1) $

但这明显太慢了！对于 $ m_1 \le 30000 $，这可能是可接受的，但远非最优。

💡 更好的做法是：仅对 $ i \in [2, \sqrt{m_1}] $ 做试除，不需要完整筛表。

👉 所以此处存在优化空间，当前实现的筛部分复杂度约为：

$ O(m_1 \log \log m_1) $ —— 类似埃氏筛前 $ \sqrt{m_1} $ 的代价

但由于 $ m_1 \le 30000
，
， \sqrt{m_1} \approx 173 $，实际影响不大。

✅ 实际耗时可控，但我们记录下来：
➡️ 此步复杂度约为 $ O(m_1 \log \log m_1) $ 或近似 $ O(m_1) $

步骤 3：计算每个质因数的幂次（在 $ m_1 $ 中）
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 = m1^m2
}
这个循环目的是统计每个质因数 $ p $ 在 $ m_1 $ 中出现多少次。
当前写法有点绕，比如用 num * prime[i][1] 来检测是否还能继续整除。
正确性没问题，但可以简化为：

int cnt = 0;
int temp = m1;
while (temp % p == 0) {
cnt++;
temp /= p;
}
prime[i][2] = cnt * m2;
不过原代码也能达到目的。

✅ 时间：最多有 $ O(\log m_1) $ 个不同质因数（一般 < 10），每个最多循环 $ \log_p m_1 $ 次 → 总体 $ O(\log m_1) $

步 m_1 $ 是质数的情况
if (size == 0) {
prime[++size][1 = m2;
}
✅ 正确：如果没找到任何因子（说明 $ m_1 $ 是质数），就把它自己作为质因数。

时间：$ O(1) $

步骤 5：对每种细胞 $ S_i $，计算所需最小时间 $ f[i] $
for (i = 1; i <= n; i++) {
for (j = 1; j <= size; j++) {
if (s[i] % prime[j][1] != 0) {
f[i] = 150000;
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 $ 种细胞 → $ O(N) $

• 内层：对每个质因数 $ p_j $，检查 $ S_i $ 是否含有该因子

  • 若无 → 不可能满足 → 设为极大值（150000）
  • 若有 → 计算 $ S_i $ 中 $ p_j $ 的指数 $ a $

    • 方法：不断乘 $ p_j $ 直到不能整除 $ S_i $

    • 实际上应改为：

      int a = 0;
      long long tmp = s[i];
      while (tmp % p == 0) {
          a++;
          tmp /= p;
      }
      

    • 原代码使用模运算判断 s[i] % (num * p)，虽然可行，但容易溢出（num * p 可能超过 int）

• 得到 $ a $：即 $ S_i $ 中含 $ p_j^a $

• 那么 $ S_i^t $ 含 $ p_j^{a \cdot t} $

• 要求：$ a \cdot t \geq e_j $，其中 $ e_j = \text{prime}[j][2] $

• 解得：$ t \geq \lceil e_j / a \rceil $

• 使用技巧：an = (e - 1)/a + 1 → 等价于向上取整

然后取所有质因子中所需时间的最大值（因为必须同时满足所有质因子）→ $ f[i] = \max_j \left\lceil \frac{e_j}{a_j} \right\rceil $

✅ 正确！

时间复杂度：

• 外层：$ O(N) $
• 内层：最多 $ O(\text{size}) = O(\log m_1) \le 10 $
• 每个内部 while 最多跑 $ \log_{p}(S_i) \le \log_2(2\times10^9) \approx 30 $
• 所以内层总时间：$ O(\text{质因数个数} \times \log S_i) = O(1) $

✅ 总时间：$ O(N) $

---

步骤 6：取最小答案

for (i = 1; i <= n; i++)
    if (ans > f[i]) ans = f[i];
if (ans == 150000) printf("-1");
else printf("%d", ans);
✅ $ O(N) $