讲解

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

// 全局变量定义
int n, m1, m2; // n:细胞种类数；m1,m2: M = m1^m2
int ans = 150000; // 最终答案（最小时间t），初始化为较大值
int s[10001]; // s[i]：第i种细胞每秒分裂后的数量
int f[10001]; // f[i]：第i种细胞满足条件的最小时间t，无效细胞标记为150000
bool p[30001]; // 埃氏筛法数组，用于标记质数（辅助m1的质因数分解）
int prime[501][3]; // 存储m1的质因数信息：prime[j][1]为质因数p_j，prime[j][2]为指数要求e_j*m2
int size = 0; // 质因数的个数

int main(void) {
// 初始化筛法数组（默认所有数为质数，后续筛除）
memset(p, 1, sizeof(p));
// 初始化f数组（默认所有细胞无效，后续更新有效细胞的时间）
memset(f, 0, sizeof(f));

// 输入基本参数
scanf("%d%d%d", &n, &m1, &m2);

// 特殊情况：若m1=1，则M=1^m2=1，任何细胞1秒后即可均分（1个细胞也能分入1个试管）
if (m1 == 1) {
    printf("0");
    return 0;
}

// 输入每种细胞的分裂数s[i]
for (int i = 1; i <= n; i++) {
    scanf("%d", &s[i]);
}

// ======================== 第一步：分解m1的质因数 ========================
// 对m1进行质因数分解，得到m1 = p1^e1 * p2^e2 * ... * pk^ek
int xx = floor(sqrt(m1));  // 质因数分解只需遍历到sqrt(m1)
for (int i = 2; i <= xx; i++) {
    if (p[i]) {  // i是质数（未被筛除）
        // 若i是m1的质因数，记录初始指数为1（后续会更新实际指数）
        if (m1 % i == 0) {
            prime[++size][1] = i;  // 存储质因数p_j
            prime[size][2] = 1;    // 临时存储指数e_j（初始为1）
        }
        // 埃氏筛法：筛除i的倍数（标记为非质数）
        int tim = 2;
        while (tim * i <= m1) {
            p[tim * i] = 0;
            tim++;
        }
    }
}

// 修正质因数的指数：计算m1中每个质因数的实际指数e_j，并乘以m2得到M的指数要求e_j*m2
for (int i = 1; i <= size; i++) {
    int num = prime[i][1];  // 当前质因数p_j
    // 计算m1中p_j的指数e_j（初始为1，通过循环累乘p_j直到不能整除）
    while (m1 % (num * prime[i][1]) == 0) {
        num *= prime[i][1];
        prime[i][2]++;  // 指数e_j递增
    }
    // M = m1^m2，因此指数要求为e_j * m2
    prime[i][2] *= m2;
}

// 特殊情况：若m1是质数（未被分解，size仍为0），则其质因数为自身，指数要求为m2
if (size == 0) {
    prime[++size][1] = m1;
    prime[size][2] = m2;
}

// ======================== 第二步：计算每种细胞的最小时间t ========================
for (int i = 1; i <= n; i++) {  // 遍历每种细胞
    for (int j = 1; j <= size; j++) {  // 检查该细胞是否包含所有质因数p_j
        // 若细胞i的分裂数s[i]不包含质因数p_j，则该细胞无效
        if (s[i] % prime[j][1] != 0) {
            f[i] = 150000;  // 标记为无效（150000为预设的无效值）
            break;          // 无需检查其他质因数，直接处理下一个细胞
        }

        // 计算s[i]中质因数p_j的指数c_j（即s[i] = ... * p_j^c_j * ...）
        int tim = 1;               // 指数c_j的计数（初始为1）
        long long num = prime[j][1];  // 累乘p_j，避免整数溢出用long long
        while (s[i] % (num * prime[j][1]) == 0) {  // 若s[i]能整除p_j^(tim+1)
            num *= prime[j][1];    // 累乘p_j（num = p_j^(tim+1)）
            tim++;                 // 指数c_j递增
        }

        // 计算该质因数p_j对应的最小时间t_j：t_j需满足 t_j * c_j >= e_j*m2
        // 即 t_j >= ceil( (e_j*m2) / c_j )，等价于 (e_j*m2 - 1) / c_j + 1
        int an = (prime[j][2] - 1) / tim + 1;
        // 细胞i的最小时间t为所有t_j的最大值（需同时满足所有质因数的指数要求）
        if (an > f[i]) {
            f[i] = an;
        }
    }
}

// ======================== 第三步：选择最小时间的细胞 ========================
for (int i = 1; i <= n; i++) {
    if (ans > f[i]) {  // 找所有有效细胞中最小的t
        ans = f[i];
    }
}

// 输出结果：若ans仍为150000，说明无有效细胞，输出-1；否则输出最小时间ans
printf("%d", ans == 150000 ? -1 : ans);

return 0;

}