形式化题目

给定 $N$ 个正整数 $S_1,\dots,S_N$ 和两个正整数 $m_1,m_2$。对每个 $i$ 求最小的非负整数 $t$，使得

若不存在这样的 $t$（即无论分裂多久都除不尽），记该细胞的答案为无解。在所有有解的细胞中输出最小的 $t$；若全部无解，输出 $-1$。

数据范围：$1 \leqslant N \leqslant 10000$，$1 \leqslant m_1 \leqslant 30000$，$1 \leqslant m_2 \leqslant 10000$，$1 \leqslant S_i \leqslant 2 \times 10^9$。

正解

思路

把"细胞个数能被 $M$ 均分"翻译成整除语言：培养 $t$ 秒后细胞个数是 $S_i^t$，实验能开始当且仅当

朴素想法：$M$ 最大可达 $30000^{10000}$，大数直接算整除完全不可行。逐秒模拟更是天文数字，必须走质因数分解这条路。

关键观察 1：整除性只由质因数指数决定。 $a \mid b$ 当且仅当对每个质数 $p$，$a$ 中 $p$ 的指数不超过 $b$ 中 $p$ 的指数。$M$ 的质因数集合就是 $m_1$ 的质因数集合——$m_1 \leqslant 30000$，试除即可分解；设 $m_1 = \prod p_j^{e_j}$，则 $M$ 中 $p_j$ 的指数是 $e_j \cdot m_2$。

关键观察 2：只关心 $m_1$ 的那几个质数。 $S_i$ 高达 $2 \times 10^9$，完整分解它并不必要（会超时）。$S_i^t$ 能否被 $M$ 整除，只取决于 $S_i$ 中是否含有 $m_1$ 的每个质数、以及含量有多少：若 $S_i$ 缺某个质数 $p_j$，则 $S_i^t$ 永远不含 $p_j$，无解；若 $S_i$ 中 $p_j$ 的指数是 $c_j \geqslant 1$，则 $S_i^t$ 中它是 $c_j \cdot t$，要求

对所有质数取最大值，就是这种细胞最早的实验时间。统计 $S_i$ 中某质数的指数时，边除边数，除到不整除为止，每个 $S_i$ 每个质数只需几次除法。

合并成答案：对每个 $S_i$ 算出上述 $t$，取所有有解细胞的最小值；一个都没有就输出 $-1$。

用样例 2 验证：$m_1 = 24 = 2^3 \cdot 3$，$m_2 = 1$，需求是 $\{2{:}\,3,\ 3{:}\,1\}$。$S = 30 = 2 \cdot 3 \cdot 5$：只统计 $2$ 和 $3$，得 $c_2 = c_3 = 1$，$t = \max(\lceil 3/1 \rceil, \lceil 1/1 \rceil) = 3$。$S = 12 = 2^2 \cdot 3$：$c_2 = 2,\ c_3 = 1$，$t = \max(\lceil 3/2 \rceil, \lceil 1/1 \rceil) = 2$，两秒后 $12^2 = 144 = 2^4 \cdot 3^2$，除以 $24$ 个试管每管 $6$ 个，与样例输出 $2$ 一致。两种细胞取最小值，答案 $2$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n;
int m1, m2;

// 把 m1 分解质因数，返回各质数及指数
vector<pair<int, int> > factorize(int x) {
    vector<pair<int, int> > res;
    for (int d = 2; d * d <= x; d++) {
        if (x % d == 0) {
            int e = 0;
            while (x % d == 0) { x /= d; e++; }
            res.push_back(make_pair(d, e));
        }
    }
    if (x > 1) res.push_back(make_pair(x, 1));
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m1 >> m2;
    vector<pair<int, int> > fac = factorize(m1);
    int ans = -1;
    for (int i = 0; i < n; i++) {
        int s;
        cin >> s;
        int steps = 0;
        bool ok = true;
        for (size_t fi = 0; fi < fac.size(); fi++) {
            int p = fac[fi].first;
            int e = fac[fi].second * m2;   // 需求指数
            int cnt = 0;
            while (s % p == 0) { s /= p; cnt++; }
            if (cnt == 0) { ok = false; break; }
            int t = (e + cnt - 1) / cnt;
            if (t > steps) steps = t;
        }
        if (ok && (ans < 0 || steps < ans)) ans = steps;
    }
    cout << ans << "\n";
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 08:13
# update_at: 2026-10-02 08:13

import sys
from collections.abc import Iterator


def factorize(m1: int) -> dict[int, int]:
    """把 m1 分解质因数，返回 {质数: 指数}；m1 ≤ 30000，试除到 √m1 即可。"""
    factors: dict[int, int] = {}
    d = 2
    while d * d <= m1:
        while m1 % d == 0:
            factors[d] = factors.get(d, 0) + 1
            m1 //= d
        d += 1
    if m1 > 1:  # 剩下的大于 1 的部分本身就是一个质数
        factors[m1] = factors.get(m1, 0) + 1
    return factors


def seconds_needed(s: int, need: dict[int, int]) -> int:
    """细胞 s 每秒乘以自己，至少多少秒后 s^t 含有 need 里每个质数的全部指数。

    返回 -1 表示 s 缺某个质数，无论分裂多久都凑不齐。
    只需统计 s 中 m1 的那些质数的指数，其余大质因子与整除性无关。
    """
    steps = 0
    for p, e in need.items():
        cnt = 0  # s 中质数 p 的指数
        while s % p == 0:
            s //= p
            cnt += 1
        if cnt == 0:  # s 里没有 p，s^t 永远不含 p
            return -1
        # t 秒后 s^t 有 cnt*t 个 p，要求 cnt*t ≥ e，即 t = ceil(e / cnt)
        steps = max(steps, -(-e // cnt))
    return steps


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    m1, m2 = next(data), next(data)
    # M = m1^m2，每个质数的总需求指数 = m1 中的指数 × m2
    need = {p: e * m2 for p, e in factorize(m1).items()}

    ans = -1
    for _ in range(n):
        s = next(data)
        steps = seconds_needed(s, need)
        if steps >= 0 and (ans < 0 or steps < ans):
            ans = steps  # 所有能凑齐的细胞里取最早开始的时间
    print(ans)


if __name__ == "__main__":
    solve()

复杂度

• 分解 $m_1$：试除到 $\sqrt{30000} \approx 173$，$O(\sqrt{m_1})$。
• 每个 $S_i$：对 $m_1$ 的每个质数 $p$ 做除法统计指数。$m_1 \leqslant 30000$ 的不同质因子最多 $6$ 个（$2\cdot3\cdot5\cdot7\cdot11\cdot13 = 30030$ 略超，故至多 $5$ 个，$2\cdot3\cdot5\cdot7\cdot11 = 2310$），每个质数至多除 $O(\log S_i)$ 次，单个 $S_i$ 约 $O(\log S_i)$；总计 $O(N \log S + \sqrt{m_1})$，远低于限时。

图示解析

从细胞个数到质数指数

以样例 2 的 $S = 12$、$M = 24^1 = 2^3 \cdot 3$ 为例，观察 $12^t$ 中每个需求质数的指数如何随 $t$ 增长：

$2$ 的指数每秒涨 $c_2 = 2$ 个、$3$ 的每秒涨 $1$ 个，两条"供给线"各自到达需求线 $e_j m_2$ 的时刻取最大值，就是这种细胞的最早时间：$\max(\lceil 3/2 \rceil, \lceil 1/1 \rceil) = 2$。整除判定被完全拆成了逐质数的"供给追需求"比较，这也是不需要大数运算的原因。

总结

• 把"均分 $M$ 个试管"写成整除条件 $m_1^{m_2} \mid S_i^t$，用质因数指数逐项比较，避免直接计算 $30000^{10000}$ 这样的大数。
• $m_1$ 试除分解；对每个 $S_i$ 只统计 $m_1$ 的那些质数的指数，缺质数即无解，否则答案为 $\max_j \lceil e_j m_2 / c_j \rceil$。
• 全体细胞取最小值；复杂度 $O(N \log S + \sqrt{m_1})$。