把目标试管数 M=m1^m2 分解成质因子需求，再看每种细胞的分裂因子 Si 每秒能提供多少对应指数，最早时间就是这些需求的最大上取整。
OJ: luogu
题目 ID: P1069
难度:普及+/提高
标签:数论质因数分解整除python
日期: 2026-06-20 12:13
题意
给出 N 种细胞。
第 i 种细胞经过 1 秒，会从 1 个分裂成 S_i 个；经过 t 秒后，就会变成：
S_i^t
个同种细胞。
现在要求把培养皿中的细胞平均分入：
M = m1^m2
个试管中。
也就是说，细胞总数必须被 M 整除。
问选择哪一种细胞培养，能让这个时刻最早到来；如果所有细胞都做不到，输出 -1。
思路
先看一个可以直接验证想法的小数据暴力：
#include <bits/stdc++.h>
using namespace std;
// brute.cpp：小数据暴力解。
// 对每种细胞直接模拟 S_i^t mod M 的变化，
// 找最早什么时候余数变成 0；如果余数开始循环还没变成 0，就说明无解。
int n;
long long m1, m2;
long long s[25];
long long power_small(long long a, long long b) {
long long ans = 1;
while (b--) {
ans *= a;
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
cin >> m1 >> m2;
for (int i = 1; i <= n; i++) {
cin >> s[i];
}
long long M = power_small(m1, m2);
if (M == 1) {
cout << 0 << '\n';
return 0;
}
long long ans = (long long)4e18;
for (int i = 1; i <= n; i++) {
vector<int> vis((int)M, 0);
long long rem = 1 % M;
long long t = 0;
while (!vis[(int)rem]) {
vis[(int)rem] = 1;
if (rem == 0) {
ans = min(ans, t);
break;
}
rem = rem * (s[i] % M) % M;
t++;
}
}
if (ans == (long long)4e18) {
cout << -1 << '\n';
} else {
cout << ans << '\n';
}
return 0;
}brute.cpp 直接模拟：
- 当前细胞数对
M的余数是多少 - 每过一秒就乘一个
S_i - 如果余数第一次变成
0，就说明这时能整除M
这个思路很贴近题意，但正式数据里 M 大到根本存不下，显然不能这样做。
关键转化：整除只和质因子指数有关
把：
M = m1^m2
先做质因数分解。
假设：
m1 = p1^a1 * p2^a2 * ...
那么：
M = p1^(a1*m2) * p2^(a2*m2) * ...
也就是说，最终需要的只是每个质因子的指数够不够。
一种细胞在 t 秒后能提供什么？
如果第 i 种细胞的分裂因子 S_i 中，某个质因子 p 的指数是 c，那么：
S_i^t
里这个质因子的指数就是：
c * t
所以只要满足：
c * t >= need
这个质因子的需求就够了。
因此对某个细胞来说，最早可行时间就是：
max( ceil(need_j / cnt_j) )
其中：
need_j表示M对第j个质因子的需求指数cnt_j表示S_i中这个质因子的指数
如果某个必须的质因子在 S_i 里一次都没有出现，那这类细胞永远无解。
最后怎么选？
对每一种细胞都算出：
- 它是否可行
- 如果可行，最早是多少秒
最后取最小值即可。
特殊情况：M = 1
如果 m1 = 1，那么 M = 1。
初始时只有 1 个细胞，本来就能整除 1，所以答案直接是 0。
Python 知识
factorize(base, exponent)在分解m1时直接把指数乘上m2，无需构造巨大的M。for ... else表达“所有必须质因子都检查成功”：中途break的细胞不会进入else。(required+available-1)//available是整数上取整模板。- 用
None表示尚无可行细胞，避免设置超大哨兵。 /home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：任意精度整数与哨兵状态。/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：批量整数读取。
代码
import sys
def factorize(number, multiplier):
factors = []
prime = 2
while prime * prime <= number:
if number % prime == 0:
exponent = 0
while number % prime == 0:
number //= prime
exponent += 1
factors.append((prime, exponent * multiplier))
prime += 1
if number > 1:
factors.append((number, multiplier))
return factors
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
base, exponent = data[1:3]
factors = factorize(base, exponent)
if not factors:
print(0)
return
answer = None
for cell in data[3:3 + n]:
required_time = 0
for prime, required in factors:
available = 0
value = cell
while value % prime == 0:
value //= prime
available += 1
if available == 0:
break
required_time = max(required_time, (required + available - 1) // available)
else:
answer = required_time if answer is None else min(answer, required_time)
print(-1 if answer is None else answer)
if __name__ == "__main__":
main()复杂度
- 时间复杂度：
- 空间复杂度：
其中 k 是 m1 的不同质因子个数，实际非常小。
总结
这题本质不是在模拟细胞个数，而是在比较“质因子指数增长速度”。
一旦把 M 和 S_i 都放到质因数分解的视角下，问题就会变成一个很直接的最大值计算。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
