还有样例和一些自制的数据都过了
by kangjingcheng @ 2021-08-27 23:32:44
```cpp
//P1069 [NOIP2009 普及组] 细胞分裂
/*
本质：数学--分解质因数
试管：m1^m2 = (p1^q1*p2^q2....)^m2 要能整除 细胞分裂t次后的数量
细胞：si^t = (r1^y1*r2^y2....)^t
必有：p1、p2....在r1、r2...中都存在 且 qi*m2 <=ri*t
t = max(ceil(qi*m2/ri))
我们需要求出满足上述条件的分裂次数t的最小值
由于满足条件的分裂次数t可能不存在，所以需要设一个上限，保证代码效率。
如何确定这个上限呢？
t = max(ceil(qi*m2/ri)) ，qi是30000以内的质因数的幂次，最大为log(2,30000)
所以，qi*m2 最大为 log(2,30000)*10000 <15*10000=150000
将t的上限设为 200000绝对没有问题。
*/
#include <cstdio>
#include <unordered_map>
using namespace std;
const int N = 2e5;
unordered_map<int, int> get(int x)
{
unordered_map<int, int> res;
for (int i = 2; i <= x / i; ++i)
if (x % i == 0)
{
int s = 0;
while (x % i == 0) x /= i, s++;
res[i] = s;
}
if (x > 1) res[x] = 1;
return res;
}
int main()
{
int n, m1, m2;
scanf("%d%d%d", &n, &m1, &m2);
unordered_map<int, int> a = get(m1);
int res = N;
while (n--)
{
int x;
scanf("%d", &x);
unordered_map<int, int> b = get(x);
int t = 0;
for (unordered_map<int, int>::iterator it = a.begin(); it != a.end(); it++)
{
int k = it->first, v = it->second;
if (!b.count(k))
{
t = N;
break;
}
else
{
t = max(t, (v * m2 + b[k] - 1) / b[k]);
}
}
res = min(res, t);
}
if (res == N) res = -1;
printf("%d\n", res);
return 0;
}
```
by Tianxn @ 2021-08-30 16:32:25