细胞分裂题解

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 分解质因数，返回 map<质数, 指数>
map<ll, ll> factorize(ll x) {
    map<ll, ll> res;
    for (ll i = 2; i * i <= x; i++) {
        while (x % i == 0) {
            res[i]++;
            x /= i;
        }
    }
    if (x > 1) res[x]++;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    ll m1, m2;
    cin >> n >> m1 >> m2;
    
    // 分解 M = m1^m2 的质因数
    // 先分解 m1，然后指数乘以 m2
    map<ll, ll> mFactors = factorize(m1);
    for (auto& [p, exp] : mFactors) {
        exp *= m2;  // M 中质因子 p 的指数
    }
    
    // 如果 m1 = 1，则 M = 1，任何数都能被 1 整除，答案为 0
    if (m1 == 1) {
        cout << 0 << endl;
        return 0;
    }
    
    ll ans = LLONG_MAX;
    
    for (int i = 0; i < n; i++) {
        ll s;
        cin >> s;
        
        // 分解 S_i 的质因数
        map<ll, ll> sFactors = factorize(s);
        
        ll needTime = 0;
        bool valid = true;
        
        // 检查 M 的每个质因子
        for (auto& [p, needExp] : mFactors) {
            // S_i 必须包含质因子 p
            if (sFactors.find(p) == sFactors.end()) {
                valid = false;  // S_i 没有这个质因子，无法满足
                break;
            }
            
            ll haveExp = sFactors[p];  // S_i 中 p 的指数
            // 需要 t * haveExp >= needExp，即 t >= ceil(needExp / haveExp)
            ll t = (needExp + haveExp - 1) / haveExp;  // 向上取整
            needTime = max(needTime, t);
        }
        
        if (valid) {
            ans = min(ans, needTime);
        }
    }
    
    if (ans == LLONG_MAX) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }
    
    return 0;
}