题解（详细）

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// 质因数分解结果的结构体
struct Factor {
    int p;  // 质因数
    long long cnt;  // 质因数的指数
};

// 对x进行质因数分解，返回分解结果
vector<Factor> factorize(int x) {
    vector<Factor> res;
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            int cnt = 0;
            while (x % i == 0) {
                cnt++;
                x /= i;
            }
            res.push_back({i, (long long)cnt});
        }
    }
    if (x > 1) {
        res.push_back({x, 1LL});
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    
    int m1, m2;
    cin >> m1 >> m2;
    
    // 特殊情况：m1=1时，M=1^m2=1，任何细胞都可以在0秒完成
    if (m1 == 1) {
        cout << 0 << endl;
        return 0;
    }
    
    // 对m1进行质因数分解
    vector<Factor> m_factors = factorize(m1);
    // 计算M=m1^m2的质因数指数
    for (auto& f : m_factors) {
        f.cnt *= m2;
    }
    
    int min_time = INT_MAX;  // 记录最小时间
    
    for (int i = 0; i < N; ++i) {
        long long S;
        cin >> S;
        
        bool valid = true;
        int max_t = 0;  // 当前细胞需要的最小时间
        
        for (const auto& f : m_factors) {
            int p = f.p;
            long long required = f.cnt;
            
            // 计算S中p的指数
            long long cnt = 0;
            while (S % p == 0) {
                cnt++;
                S /= p;
            }
            
            // 如果S中没有p这个质因数，该细胞无效
            if (cnt == 0) {
                valid = false;
                break;
            }
            
            // 计算需要多少秒才能满足指数要求
            // t = ceil(required / cnt)
            int t = (required + cnt - 1) / cnt;
            if (t > max_t) {
                max_t = t;
            }
        }
        
        // 如果细胞有效，更新最小时间
        if (valid) {
            if (max_t < min_time) {
                min_time = max_t;
            }
        }
    }
    
    // 输出结果
    if (min_time == INT_MAX) {
        cout << -1 << endl;
    } else {
        cout << min_time << endl;
    }
    
    return 0;
}

问题深度解析
核心数学原理
问题转化：判断Sᵗ是否能被M=m₁^{m₂整除，等价于判断S的质因数分解中，每个质因数的指数是否≥m₁}m₂对应质因数的指数。

关键推导：

对m₁进行质因数分解：m₁ = p₁^a₁ * p₂^a₂ * ... * p_k^a_k
则M=m₁^m₂ = p₁^(a₁m₂) * p₂^(a₂m₂) * ... * p_k^(a_k*m₂)
对于细胞Sᵢ，若Sᵢ包含m₁的所有质因数，则存在最小t使得Sᵢ^t包含M的所有质因数
若Sᵢ不包含m₁的某个质因数，则永远无法满足条件