这道题是多组数据,那些第十个点错的人看过
2025-07-10 16:48:55
发布于:广东
4阅读
0回复
0点赞
#include <iostream>
#include <vector>
#include <climits>
#include <cmath>
using namespace std;
struct Factor {
int prime;
int count;
};
vector<Factor> factorize(int m1) {
vector<Factor> factors;
if (m1 == 1) {
return factors;
}
for (int p = 2; p * p <= m1; ++p) {
if (m1 % p == 0) {
int cnt = 0;
while (m1 % p == 0) {
m1 /= p;
cnt++;
}
factors.push_back({p, cnt});
}
}
if (m1 > 1) {
factors.push_back({m1, 1});
}
return factors;
}
int computeMinTime(int Si, const vector<Factor>& m1_factors, int m2) {
if (Si == 1) {
return -1;
}
int max_time = 0;
for (const auto& factor : m1_factors) {
int p = factor.prime;
int a = factor.count * m2;
int b = 0;
int temp = Si;
while (temp % p == 0) {
temp /= p;
b++;
}
if (b == 0) {
return -1;
}
int t = (a + b - 1) / b; // Equivalent to ceil(a / b)
if (t > max_time) {
max_time = t;
}
}
return max_time;
}
int main() {
int N;
while (cin >> N) {
int m1, m2;
cin >> m1 >> m2;
vector<int> S(N);
for (int i = 0; i < N; ++i) {
cin >> S[i];
}
vector<Factor> m1_factors = factorize(m1);
if (m1 == 1) {
cout << 0 << endl << endl;
continue;
}
int min_time = INT_MAX;
for (int Si : S) {
int time = computeMinTime(Si, m1_factors, m2);
if (time != -1 && time < min_time) {
min_time = time;
}
}
if (min_time != INT_MAX) {
cout << min_time << endl;
} else {
cout << -1 << endl;
}
cout << endl; // Separate test cases with a blank line
}
return 0;
}
这里空空如也
有帮助,赞一个