Hanks 博士是 **（Bio-Tech，生物技术）领域的知名专家。现在，他正在为一个细胞实验做准备工作：培养细胞样本。 Hanks 博士手里现在有  𝑁  种细胞，编号从  1 ∼ 𝑁 ，一个第  𝑖  种细胞经过  1  秒钟可以分裂为  𝑆 𝑖  个同种细胞（ 𝑆 𝑖  为正整数）。现在他需要选取某种细胞的一个放进培养皿，让其自由分裂，进行培养。一段时间以后，再把培养皿中的所有细胞平均分入  𝑀  个试管，形成  𝑀  份样本，用于实验。Hanks 博士的试管数  𝑀  很大，普通的计算机的基本数据类型无法存储这样大的  𝑀  值，但万幸的是， 𝑀  总可以表示为  𝑚 1  的  𝑚 2  次方，即  𝑀 = 𝑚 1 𝑚 2 ，其中  𝑚 1 , 𝑚 2  均为基本数据类型可以存储的正整数。 注意，整个实验过程中不允许分割单个细胞，比如某个时刻若培养皿中有  4  个细胞，Hanks 博士可以把它们分入  2  个试管，每试管内  2  个，然后开始实验。但如果培养皿中有  5  个细胞，博士就无法将它们均分入  2  个试管。此时，

题意理解 细胞分裂：第 \( i \) 种细胞 1 秒后数量乘以 \( S_i \)。 初始 1 个细胞，经过 \( t \) 秒后数量为 \( S_i^t \)。 要求 \( S_i^t \) 能被 \( M = m_1^{m_2} \) 整除，且 \( t \) 最小。 --- 关键转化 设 \( m_1 \) 的质因数分解为： \[ m_1 = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k} \] 则 \[ M = m_1^{m_2} = p_1^{a_1 m_2} p_2^{a_2 m_2} \dots p_k^{a_k m_2} \] 要求 \( S_i^t \) 能被 \( M \) 整除，等价于对每个质因数 \( p_j \)， \[ v_{p_j}(S_i^t) \ge a_j m_2 \] 其中 \( v_p(x) \) 表示 \( x \) 中质因数 \( p \) 的指数。 由于 \( v_p(S_i^t) = t \cdot v_p(S_i) \)，所以条件为： \[ t \cdot v_p(S_i) \ge a_j m_2 \] 对每个 \( p_j \) 成立。 --- 情况分析 1. 如果 \( v_p(S_i) = 0 \)（即 \( S_i \) 不含质因数 \( p_j \)），则左边恒为 0，不可能 ≥ 正数 \( a_j m_2 \)，除非 \( a_j m_2 = 0 \)（但 \( m_1 \) 含 \( p_j \) 时 \( a_j > 0 \)）。 所以只要 \( m_1 \) 有某个质因数 \( p_j \) 在 \( S_i \) 中不出现，这种细胞就不可能满足要求。 2. 如果 \( v_p(S_i) > 0 \)，则对质因数 \( p_j \) 需要 \[ t \ge \lceil \frac{a_j m_2}{v_p(S_i)} \rceil \] 对 \( m_1 \) 的所有质因数 \( p_j \)，取最大值： \[ t_i = \max_{j} \left\lceil \frac{a_j m_2}{v_p(S_i)} \right\rceil \] 这就是第 \( i \) 种细胞所需的最少时间。 如果 \( m_1 = 1 \)，则 \( M = 1 \)，任何细胞 0 秒即可整除，答案为 0。 --- 算法步骤 1. 对 \( m_1 \) 做质因数分解，得到 \( (p_j, a_j) \)。 2. 对每个 \( S_i \)： - 检查 \( m_1 \) 的每个质因数 \( p_j \) 是否都出现在 \( S_i \) 的质因数中（即 \( v_p(S_i) > 0 \)）。 如果不是，则这种细胞不可行。 - 如果都出现，计算 \[ t_{i,j} = \lceil \frac{a_j m_2}{v_p(S_i)} \rceil \] 取 \( t_i = \max_j t_{i,j} \)。 3. 所有可行的 \( t_i \) 中取最小值，若没有可行的则输出 -1。 --- 样例验证 样例 1： \( N=1, m_1=2, m_2=1, S_1=3 \) \( m_1 = 2^1 \)，质因数 2。 \( S_1 = 3 \)，\( v_2(3) = 0 \)，不含质因数 2，不可能整除 \( 2^1 \)，输出 -1。 样例 2： \( N=2, m_1=24, m_2=1, S=[30,12] \) \( m_1 = 24 = 2^3 \cdot 3^1 \) \( a_1=3, a_2=1, m_2=1 \) - 对 \( S_1=30 = 2 \cdot 3 \cdot 5 \) \( v_2=1, v_3=1 \) \( t_{1,2} = \lceil 3/1 \rceil = 3 \) \( t_{1,3} = \lceil 1/1 \rceil = 1 \) \( t_1 = \max(3,1) = 3 \) - 对 \( S_2=12 = 2^2 \cdot 3^1 \) \( v_2=2, v_3=1 \) \( t_{2,2} = \lceil 3/2 \rceil = 2 \) \( t_{2,3} = \lceil 1/1 \rceil = 1 \) \( t_2 = \max(2,1) = 2 \) 最小 \( t = 2 \)，输出 2。 --- 代码实现 ```cpp #include <iostream> #include <vector> #include <cmath> #include <climits> using namespace std; // 分解质因数 vector<pair<int, int>> factorize(int x) { vector<pair<int, int>> res; for (int i = 2; i * i <= x; i++) { if (x % i == 0) { int cnt = 0; while (x % i == 0) { x /= i; cnt++; } res.push_back({i, cnt}); } } if (x > 1) res.push_back({x, 1}); return res; } int main() { int N, m1, m2; cin >> N >> m1 >> m2; vector<pair<int, int>> m1_factors = factorize(m1); // 每个质因数的指数乘以 m2 for (auto &p : m1_factors) { p.second *= m2; } int ans = INT_MAX; for (int i = 0; i < N; i++) { int s; cin >> s; bool feasible = true; int max_t = 0; for (auto &pf : m1_factors) { int p = pf.first; int need = pf.second; // 计算 s 中 p 的指数 int cnt = 0; int temp = s; while (temp % p == 0) { temp /= p; cnt++; } if (cnt == 0) { feasible = false; break; } // 需要 t * cnt >= need int t_needed = (need + cnt - 1) / cnt; // 向上取整 if (t_needed > max_t) { max_t = t_needed; } } if (feasible && max_t < ans) { ans = max_t; } } if (ans == INT_MAX) { cout << -1 << endl; } else { cout << ans << endl; } return 0; } ``` [2026-01-11 17:55:17 | AI问答 | 1657点数解答]