思路：质因数分解

本题选出的细胞，必须能均分$m1^{m2}$，也就是$(s[i]^x)|(m1^{m2})$

根据分解定律，$m_1$分解质因数后，例如分解$m_1=a_1^{x_1}*a_2^{x_2}$

如果$s[i]$想要在日后分裂中可以平分进去，它必须也有$a_1,a_2$这两个因子。

然后如果有的话，在分别乘以$x_1,x_2$。通过计算比较最大的值就是它需要多少时间去均分进去。

拿样例来说$24=2^3*3$

$30=2*3*5$，因此需要$3$的时间。$12=2*2*3$ 需要$2$的时间。注意一定要能分解完$m_1$的所有因子

这个方案才可以成功。

#include <bits/stdc++.h>
using namespace std;
int n, m1, m2, s[10005];
struct node
{
	int x, y;
};
vector<node> v;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m1 >> m2;
	for (int i = 1; i <= n; i++)
		cin >> s[i];
	if (m1 == 1)//特判m1==1的时候，不需要任何时间就均分了
	{
		cout << 0;
		return 0;
	}
	for (int i = 2; i * i <= m1; i++)//分解m1的质因子
	{
		if (m1 % i == 0)
		{
			int cnt = 0;
			while (m1 % i == 0)
			{
				m1 /= i;
				cnt++;
			}
			v.push_back((node){i, m2 * cnt});
		}
	}
	if (m1 != 1)
	{
		v.push_back((node){m1, m2});
	}
	bool flag = false;
	int num = 0x3f3f3f3f;
	for (int i = 1; i <= n; i++)
	{
		int ans1 = -1, ans = 0, q = 0;
		bool flag1 = false;
		for (int j = 0; j < v.size(); j++)//暴力验证每一个数字
		{
			if (s[i] % v[j].x == 0)
			{
				q++;//统计s[i]的分解次数，只有分解了所有的m1质因子这个才能均分
				int cnt = 0;
				while (s[i] % v[j].x == 0)//对m1的因子进行检查看能否分解
				{
					s[i] /= v[j].x;
					cnt++;
				}
				if (cnt < v[j].y)//统计当前这个分解出来的因子需要分裂几次
				{
					ans = max((int)ceil(v[j].y * 1.0 / cnt), ans);
				}
				else
					ans = max(ans, cnt);
			}
			if (q == v.size())//分解了所有的就去求最大值
			{
				flag = flag1 = true;
				ans1 = max(ans1, ans);
			}
		}
		if (flag1)//所有的最大值去求最小值
		{
			num = min(num, ans1);
		}
	}
	if (!flag)
		cout << -1;
	else
		cout << num;
	return 0;
}

好难，卡了我整整半个小时

#include <bits/stdc++.h>
using namespace std;
int n, m1, m2, a[10005], ans = 0x7fffffff, b[30005], sum;
int func(int a, int b)
{
	int sum = 0;
	while (a > 0 && a % b == 0)
	{
		a /= b;
		sum++;
	}
	return sum;
}
int main()
{
	cin >> n >> m1 >> m2;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 2; i <= m1; i++)
	{
		while (m1 > 0 && m1 % i == 0)
		{
			m1 /= i;
			b[i]++;
		}
		b[i] *= m2;
		if (!b[i])
			sum++;
	}
	for (int i = 1; i <= n; i++)
	{
		bool flag = true;
		int sec = 0, cnt = 0;
		for (int j = 2; j <= 30000; j++)
		{
			if (b[j])
			{
				if (a[i] % j == 0)
				{
					cnt++;
					int tmp = func(a[i], j);
					sec = max(sec, (b[j] + tmp - 1) / tmp);
				}
				else
				{
					flag = false;
					break;
				}
				if (cnt == sum)
					break;
			}
		}
		if (flag)
			ans = min(ans, sec);
	}
	if (ans != 0x7fffffff)
		cout << ans << endl;
	else
		cout << -1 << endl;
	return 0;
}