A6细胞分裂——题解

这题因该是普及+才对呀

【做题背景】数学题，秒杀！

【算法名称】质因数分解

【算法分析】题目即要求最小的正整数 k 使得有一个 $i（1~n）$，满足 $si^k|m1^m2$。

以样例二为例，$24^1=24=2^3*3$

对于细胞一，$30=2*3*5$

要使每一个质因数均满足要求，

最小值now的计算过程为：

step 1：对于质因子2，$now=3$

step 2：对于质因子3，$now=3$

对于细胞二，$12=2^2*3$

要使每一个质因数均满足要求，

最小值now的计算过程为：

step 1：对于质因子2，$now=2$

step 2：对于质因子3，$now=2$

所以，min值为2 算法结束~~~

【注意事项】

1.对于30，质因子5没有任何用处，因为 $30^k$ 应为24的倍数。

2.把30000以内所有质数都枚举出来应该会更快。

3.质因数分解的过程千万不能写错（别忘了把 $m1$ 的质因子个数都 $*m2$ 哦）！

4.请勿抄袭题解！

贴上华丽的代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
struct Nums{
	int prime;
	int cnt;
}p[maxn];
int a[maxn];
int m1, m2;
int n;
int total = 0;
void div(int num){
	if (num == 1){
		return ;
	}
	for (int i = 2; i * i <= num; ++i){
		if (num % i == 0){
			p[++total].prime = i;
			while (num % i == 0){
				num /= i;
				p[total].cnt++;
			}
			p[total].cnt *= m2;
		}
	}
	if(num != 1){
		p[++total].prime = num;
		p[total].cnt = m2;
	}
	return ;
}
bool check(int x){
	for (int i = 1; i <= total; i++){
		if (x % p[i].prime != 0){
			return 0;
		}
	}
	return true;
}
int minn = INT_MAX;
void cultivate(int x){
	int maxx = 0;
	for (int i = 1; i <= total; i++){
		int tmp = 0;
		while (x % p[i].prime == 0){
			tmp++;
			x /= p[i].prime;
		}
		int ans = (p[i].cnt - 1) / tmp + 1;
		maxx = max(maxx, ans);
	}
	minn = min(minn, maxx);
	return ;
}
signed main(){
	cin >> n;
	cin >> m1 >> m2;
	div(m1);
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		if (check(a[i]) == 0){
			continue;
		}
		cultivate(a[i]);
	}
	if (minn == INT_MAX){
		cout << -1;
	}
	else{
		cout << minn ;
	}
	return 0;
}