题解

#include <iostream>
#include <vector>
#include <map>
#include <climits>

using namespace std;

map<int, int> primeFactors(int n) {
map<int, int> factors;
for (int i = 2; i * i <= n; i) {
while (n % i == 0) {
factors[i];
n /= i;
}
}
if (n > 1) {
factors[n]++;
}
return factors;
}

int main() {
int N;
cin >> N;

int m1, m2;
cin >> m1 >> m2;

map<int, int> M_factors = primeFactors(m1);
for (auto& [p, exp] : M_factors) {
    exp *= m2;
}

vector<int> S(N);
for (int i = 0; i < N; ++i) {
    cin >> S[i];
}

int min_time = INT_MAX;
bool found = false;

for (int i = 0; i < N; ++i) {
    if (S[i] == 1) {
        continue;
    }

    map<int, int> Si_factors = primeFactors(S[i]);
    bool valid = true;
    int current_time = 0;

    for (auto& [p, exp_M] : M_factors) {
        if (Si_factors.find(p) == Si_factors.end()) {
            valid = false;
            break;
        }
        int exp_Si = Si_factors[p];
        int time = (exp_M + exp_Si - 1) / exp_Si;
        if (time > current_time) {
            current_time = time;
        }
    }

    if (valid) {
        found = true;
        if (current_time < min_time) {
            min_time = current_time;
        }
    }
}

if (found) {
    cout << min_time << endl;
} else {
    cout << -1 << endl;
}

return 0;

}