解题思路

思路

1. 分解试管总数
   令

   $$M = m_1^{m_2}.$$

   首先对 (m_1) 做质因数分解：

   $$m_1 = \prod_{j=1}^k p_j^{a_j},$$

   则

   $$M = \prod_{j=1}^k p_j^{a_j\,m_2}.$$

2. 可行性判断
   第 (i) 种细胞每秒分裂为 (S_i) 个，(t) 秒后共有 (S_i^t) 个。要让 (S_i^t) 能被 (M) 整除，需要对每个质因子 (p_j) 满足

   $$\nu_{p_j}(S_i^t) \ge \nu_{p_j}(M) \quad\Longleftrightarrow\quad t\cdot\nu_{p_j}(S_i)\ge a_j\,m_2.$$

   若对某个 (j) 有 (\nu_{p_j}(S_i)=0) 且 (a_j m_2>0)，则该细胞类型永远不可能均分。

3. 计算最少所需时间
   若第 (i) 种细胞在所有质因子上都可行，则

   $$t_i = \max_{1\le j\le k}\Bigl\lceil \frac{a_j\,m_2}{\nu_{p_j}(S_i)}\Bigr\rceil.$$

   全局答案即

   $$\min_{1\le i\le N} t_i,$$

   若所有 (i) 均不可行，则输出 (-1)。

4. 特殊情况
   若 (m_1=1)，则 (M=1^{m_2}=1)，任何细胞在 (t=0) 时即可分配到 1 个试管，答案为 (0)。

---

复杂度分析

• 分解 (m_1)：试除到 (\sqrt{m_1})，最多 (O(\sqrt{m_1}))，其中 (m_1\le3\times10^4)。
• 对每个 (S_i)（共 (N\le10^4)）仅检查至多 (O(\log m_1)) 个质因子，因此总时间 (O(N\log m_1))。
• 内存使用 (O(N + #\text{质因子}(m_1)))，满足题目要求。