细胞分裂

题目
分解质因数

超时的代码，每次每个数字循环的次数太大了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node {
	ll coe, exp;
}bucket[1005];
ll ans;
void Get(ll x, ll b) {
	ll i = 2, len = sqrt(x);
	ans = 0;
	while(x != 1 && i <= len) {
		if(x % i == 0) {
			ll cnt = 0;
			while(x % i == 0) {
				cnt++;
				x /= i;
			}
			bucket[ans++] = {i, cnt * b};
		}
		++i;
	}
	if(x != 1) bucket[ans++] = {x, b};
}
int main() {
	ll n;
	while(~scanf("%lld", &n)) {
		ll a, b, mi = LLONG_MAX;
		scanf("%lld %lld", &a, &b);
		Get(a, b);
		while(n--) {
			ll x;
			scanf("%lld", &x);
			ll len = sqrt(x);
			ll i = 2, f = 1, res = 0, j = 0;
			while(x != 1 && i <= len && j < ans) {
				if(x % i == 0) {
					ll cnt = 0;
					while(x % i == 0) {
						cnt++;
						x /= i;
					}
					if(bucket[j].coe == i) {
						res = max(res, (ll)ceil((0.0 + bucket[j].exp) / cnt));
						++j;
					}
				}
				++i;
			}
			if(x != 1 && bucket[j].coe == x) {
				res = max(res, bucket[j].exp);
				++j;
			}
			if(j >= ans) 
				mi = min(mi, res);
		}
		printf("%lld\n", mi == LLONG_MAX? -1 : mi);
	}
	return 0;
}

AC代码，把顺序颠倒一下就可以了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node {
	ll coe, exp;
}bucket[1005];
ll ans;
void Get(ll x, ll b) {
	ll i = 2, len = sqrt(x);
	ans = 0;
	while(x != 1 && i <= len) {
		if(x % i == 0) {
			ll cnt = 0;
			while(x % i == 0) {
				cnt++;
				x /= i;
			}
			bucket[ans++] = {i, cnt * b};
		}
		++i;
	}
	if(x != 1) bucket[ans++] = {x, b};
}
ll f(ll x, ll y) {
	int cnt = 0;
	while(x % y == 0)
		cnt++,x /= y;
	return cnt;
}
int main() {
	ll n;
	while(~scanf("%lld", &n)) {
		ll a, b, mi = LLONG_MAX;
		scanf("%lld %lld", &a, &b);
		Get(a, b);
		while(n--) {
			ll x;
			scanf("%lld", &x);
			ll i, res = 0;
			for(i = 0; i < ans; ++i) {
				if(x % bucket[i].coe == 0) {
					int cnt = f(x, bucket[i].coe);
					if(bucket[i].exp % cnt == 0) {
						res = max(res, bucket[i].exp / cnt);
					}
					else {
						res = max(res, bucket[i].exp / cnt + 1);
					}
				}
				else break;
			}
			if(i >= ans) 
				mi = min(mi, res);
		}
		printf("%lld\n", mi == LLONG_MAX? -1 : mi);
	}
	return 0;
}