题目：

细胞分裂

题目解析

先看题目，肥肠的长，但是我们简化后就是设$x$是最小的使得${m_{1}}^{m_{2}}\vert {S{i}}^{x_{i}}$的整数(也有可能不存在)，求$\min(x_1, ...,x_n)$

虽说关键数字${m_{1}}^{m_{2}}$大的吓人但是你先别急

先介绍一个

有了推论的铺垫，这道题的突破口也是很明显的：
如果$m_1 = {{p_1}^{a_1}{p_2}^{a_2}...{p_s}^{a_s}}$， 那么${m_1}^{m_2} = {{p_1}^{a_1m_2}{p_2}^{a_2m_2}...{p_s}^{a_sm_2}}$。接下来只需要解决题意中的 $x_i$ 的求解。
由推论可以得到， 若${m_1}^{m2}$中的每个质因子的幂次都比${S_{1}}^{x_i}$ 小时，${m_1}^{m2}\vert {S_{1}}^{x_i}$成立。${S_{1}}^{x_i}$ 中的质因子是否出现由 $S_i$ 决定，而质因子出现了几次主要由 $x_i$ 决定。若 $S_i = {{p_1}^{e_1}{p_2}^{e_2}...{p_s}^{e_s}{p_{s+1}}^{e_{s+1}}...{p_{s+r}}^{e_{s+r}}}$（${p_{s+1}}^{e_{s+1}}$ 到 ${p_{s+r}}^{e_{s+r}}$ 表示与 $m_1$ 无关的质因子），那么$x_i$ 应该使得 $1 \leq j \leq s$ 的 $j$，满足 $a_jm_2 \leq e_jx_i$
所以从 $m_1$中的每个质因子 $p_j$ 出发: 如果这个$S_i$ 不能整除 $p_j$，则说明 $S_i$ 不包含 $p_j$ 这个质因子，进而找不到题设所要求的$x_i$；如果这个$S_i$ 能整除 $p_j$，那么只需要求出对应的$e_j$，就能算出第 $j$个质因子， 要求 $x_i$ 不小于 $\lceil \frac {a_jm_2}{e_j} \rceil$，在对所有的这样的要求取最大值，就都得到了 $x_i$。最后对所有合法的 $x_i$ 取最小值就是答案

代码

#include <bits/stdc++.h>
using namespace std;

unordered_map<int, int> pri;
int m1, m2, n, ans = 2147483647, x;

void fenjie (int a) {
	for (int i = 2; i <= sqrt(a); i++) {
		if(a % i == 0) {
			pri[i]++;
			a /= i;
			i--;
		}
	}
	if(a > 1) {
		pri[a]++;
	}
}

int main() {
	cin >> n >> m1 >> m2;
	fenjie(m1);
	while(n--) {
		cin >> x;
		int res = 0;
		for (pair<int, int> p : pri) {
			int t = p.first;
			if(x % t != 0) {
				res = -1;
				break;
			} else {
				int cnt = 0;
				for(; x % t == 0; x /= t) {
					cnt++;
				}
				res = max(res, (int)ceil(m2 * 1.0 * p.second / cnt));
			}
		}
		if(res >= 0) {
			ans = min(ans, res);
		}
	}
	if (ans >= 2147483647) {
		cout << -1 << endl;
	} else {
		cout << ans << endl;
	}
	return 0;
}