这道题是多组数据,那些第十个点错的人看过
2025-07-10 16:48:55
发布于:广东
9阅读
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;
}
这里空空如也






有帮助,赞一个