148 lines
6.1 KiB
Markdown
148 lines
6.1 KiB
Markdown
## [$AcWing$ $439$. 细胞分裂](https://www.acwing.com/problem/content/441/)
|
||
|
||
### 一、预备知识
|
||
[整数除法向上取整](https://www.cnblogs.com/littlehb/p/15213429.html)
|
||
|
||
### 二、题意分析
|
||
|
||
* 细胞分裂到一定的数量，可以 **平均分布** 到各个试管中。
|
||
|
||
这句话的意思就是说：细胞数量能 **整除** 试管的数量，并且是 **最少的分裂步数**。
|
||
|
||
试管的数量$M=m_1^{m_2}$,其中$m_1<=3000,m_2<=1000$，这玩意太大了，不可能直接算！既然不能直接算，就要想想 [算术基本定理中关于整除的相关内容](https://www.cnblogs.com/littlehb/p/15205576.html)：
|
||
|
||
说白了，就是把试管数分解质数因子，不光要记录质数因子有哪些，还要记录每个质数因数有多少个。
|
||
|
||
* <font color='red'>遍历每种细胞，拿试管个数的每一个质因数对细胞的每秒分裂个数进行取模，模如果不为0，则表示不管咋分裂，最后也不出来这个试管数量的倍数！</font>
|
||
|
||
* <font color='red'>如果通过了检查，那么一定是可以通过不断的分裂成为试管数量的倍数的。</font>
|
||
|
||
|
||
### $Code$
|
||
```cpp {.line-numbers}
|
||
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int INF = 0x3f3f3f3f;
|
||
const int N = 1010;
|
||
/*
|
||
解析：
|
||
这一题其实就是分解质因数，把试管数和每种细胞分解质因数，试管有的质因数细胞也要有，才能在一段时间后装入试管。
|
||
|
||
分解质数因子的结果(对试管的数量进行质数因子分解的结果)
|
||
*/
|
||
struct Node {
|
||
int number; // 质数因子
|
||
int count; // 质数因子的个数
|
||
} a[N];
|
||
int al; // 这个al是配合a[N]使用的下标变量
|
||
|
||
// 试管的总数 M=m1^m2
|
||
int m1; // 试管的数量底
|
||
int m2; // 试管的数量幂
|
||
int n; // 细胞种数
|
||
|
||
// 预求最小，先设最大
|
||
int mi = INF;
|
||
|
||
/**
|
||
测试数据
|
||
2
|
||
24 1
|
||
30 12
|
||
|
||
2 两种细胞
|
||
24 1 m1=24,m2=1 ，pow(m1,m2)=pow(24,1)=24 试管个数
|
||
30 12 第一种细胞，每秒分裂30个；第二种细胞，每秒分裂12个。
|
||
|
||
答案：2
|
||
|
||
解析：
|
||
第1种细胞，每秒分裂30个。24分解质因数为=2*2*2*3，
|
||
而30%2=0，30%3=0，所以30肯定可以通过不断分裂成为24的个倍数。
|
||
30里面有1个2，1个3，1个5。要想达到3个2，需要3个30相乘。按本题上下文来说，就是分裂3次。
|
||
乘上一个30，就可以多出一个2的因子，需要3个，就是需要3秒。
|
||
|
||
第2种细胞，从1个细胞开始，第一秒分裂为12个，第二秒就是 12*12个，也就是144个。而144/24=6，
|
||
就是说明此时可以平均分布到每个试管中了。
|
||
*/
|
||
int main() {
|
||
// 读入
|
||
cin >> n >> m1 >> m2;
|
||
|
||
// 对x进行分解质数因子
|
||
for (int i = 2; i <= m1; i++) {
|
||
if (m1 % i == 0) { // 如果m1可以整除因子i
|
||
a[++al].number = i; // a数组从下标1开始，记录数字
|
||
while (m1 % i == 0) { // 采用能除尽除的思路
|
||
m1 /= i;
|
||
a[al].count++; // 记录质数因子的个数
|
||
}
|
||
a[al].count *= m2; // 换算成试管的总数,因为原题是m1^m2,所以可以分解成每个质数因子的m2次方的乘积
|
||
}
|
||
}
|
||
|
||
// 遍历n类细胞，看看谁的分裂时间最快(就是求最小值)能平均分配到试管中
|
||
while (n--) {
|
||
int s; // 每秒钟的分裂个数
|
||
cin >> s;
|
||
|
||
// 是否可以成功装入容器的标识
|
||
bool flag = true;
|
||
// 遍历每个m1的质数因子
|
||
for (int i = 1; i <= al; i++)
|
||
// 一旦发现s在没有分裂前就没有质数因子a[i],那么就永远不可能分裂出m1^m2的倍数了
|
||
if (s % a[i].number != 0) {
|
||
flag = false;
|
||
break;
|
||
}
|
||
// 如果所有质数因子都存在，那么就一定可以通过分裂达到一定次数后，成为m1^m2的倍数
|
||
// 如果不是所有质数因子存在，那么这种细胞就需要放弃掉了，因为永远都不可能放到M个试管中去。
|
||
if (flag) {
|
||
// 这里的最大值初始化为0是有意义的，要注意，不能使用-INF，这样就成功躲过了0
|
||
int mx = 0;
|
||
|
||
// 遍历m1的每一个质数因子
|
||
for (int i = 1; i <= al; i++) {
|
||
// s中每一个质数因子出现的个数
|
||
int cnt = 0;
|
||
// 分解质因数
|
||
while (s % a[i].number == 0) {
|
||
s /= a[i].number;
|
||
cnt++;
|
||
}
|
||
/*
|
||
细胞的每秒分裂数：s
|
||
s里面质数因子a[i]的个数:cnt
|
||
想在达到或超过的质数因子a[i]的个数：a[i].count
|
||
以s=30为例，观察它当中质因子2的变化情况
|
||
0秒 1个
|
||
1秒 30个 30=2*3*5
|
||
2秒 30*30个 30*30=2*3*5*2*3*5
|
||
3秒 30*30*30个 30*30*30= 2*3*5*2*3*5*2*3*5
|
||
看出来了吧，每秒都是原来的30倍个，但因子2的增加，可是1个1个增加的。
|
||
为什么是1个呢？因为30原来的质数因子就只有1个2，如果有2个2，就是2个2个增加的。
|
||
|
||
总结一下：以30为例，因为只有1个2这个质数因子，那么，如果需要3个2，就需要分裂3秒！
|
||
如果需要a[i].count这么多个质数因子，就要找出原配带来cnt个的，经过几秒才能等于或超过。
|
||
C++的整数除法上取整~
|
||
*/
|
||
// 方法1:
|
||
// int second = (a[i].count - 1) / cnt + 1;
|
||
|
||
// 方法2:
|
||
int second = ceil(1.0 * a[i].count / cnt); // 需要多少秒
|
||
|
||
// 找出s中幂指数最大的
|
||
mx = max(mx, second);
|
||
}
|
||
mi = min(mi, mx); // 最少秒时可以装进试管
|
||
}
|
||
}
|
||
if (mi == INF)
|
||
printf("-1"); // 如果没有改变，输出-1
|
||
else
|
||
printf("%d", mi); // 输出结果
|
||
return 0;
|
||
}
|
||
``` |