A6.细胞分裂

根据题目描述，这个问题实际上是一个数学质因数分解问题。关键在于理解：细胞数量在某个时间 t 后为 S^t，需要能被 M = m1^m2 整除。

---

解题思路↓

1. 问题转换：细胞每秒分裂 S 个，t 秒后数量为 S^t。我们需要 M 能整除 S^t，即 S^t 的质因数分解必须包含 M 的所有质因数，并且每个质因数的指数不小于 M 中对应的指数。
2. 分解 M：先对 m1 进行质因数分解。由于 M = m1^m2，所以 M 的每个质因数 p 的指数是 m1 中 p 的指数乘以 m2。
3. 检查每个细胞 S：对每个给定的 S：
   • 计算 S 的质因数分解。
   • 检查 S 是否包含 M 的所有质因数。如果不包含，则这个细胞永远无法满足要求（输出 -1 的情况）。
   • 如果包含，对于 M 的每个质因数 p，设它在 m1 中的指数为 a，则在 M 中的指数为 a * m2。设 p 在 S 中的指数为 b，那么我们需要找到最小的 t，使得 b * t >= a * m2。对于这个质因数 p，所需的最小 t 为 ceil( (a * m2) / b )（ceil 表示向上取整）。
   • 对 M 的所有质因数都计算这样的 t，然后取最大值（因为需要同时满足所有质因数的条件）。这个最大值就是使用该细胞所需的最少时间。
4. 求最终答案：对所有细胞计算出的最少时间，取最小值。如果所有细胞都无法满足要求，则输出 -1。

---

代码实现（all AC，可放心食用）

#include <cstdio>
#include <cmath>
#include <climits>

struct Factor {
    int prime;  
    int count;  
};

Factor m1_factors[100]; 
int factor_cnt = 0;     

void factorize(int m1) {
    factor_cnt = 0;
    int temp = m1;
    for (int i = 2; i * i <= temp; i++) {
        if (temp % i == 0) {
            m1_factors[factor_cnt].prime = i;
            m1_factors[factor_cnt].count = 0;
            while (temp % i == 0) {
                temp /= i;
                m1_factors[factor_cnt].count++;
            }
            factor_cnt++;
        }
    }
    if (temp > 1) {
        m1_factors[factor_cnt].prime = temp;
        m1_factors[factor_cnt].count = 1;
        factor_cnt++;
    }
}

int main() {
    int N, m1, m2;
    scanf("%d", &N);
    scanf("%d %d", &m1, &m2);

    factorize(m1);

    int ans = INT_MAX;

    for (int i = 0; i < N; i++) {
        int S;
        scanf("%d", &S);

        int cell_time = 0;
        bool valid = true;

        for (int j = 0; j < factor_cnt; j++) {
            int p = m1_factors[j].prime;
            int a = m1_factors[j].count; 
            int total_needed = a * m2;

            int b = 0;
            while (S % p == 0) {
                S /= p;
                b++;
            }

            if (b == 0) {
                valid = false;
                break;
            }

            int t_needed = (total_needed + b - 1) / b; 
            if (t_needed > cell_time) {
                cell_time = t_needed;
            }
        }

        if (valid && cell_time < ans) {
            ans = cell_time;
        }
    }

    if (ans == INT_MAX) {
        printf("-1\n");
    } else {
        printf("%d\n", ans);
    }

    return 0;//好习惯
}

代码说明

• 数据结构：使用结构体数组 m1_factors 存储 m1 的质因数分解结果。
• 质因数分解：factorize 函数对 m1 进行质因数分解。
• 主要逻辑：对于每个细胞 S，检查 M 的所有质因数是否都存在于 S 中，并计算所需的最少时间。
• 向上取整：使用 (total_needed + b - 1) / b 来计算 ceil(total_needed / b)，避免使用浮点数。
• 结果输出：如果所有细胞都无效，则输出 -1；否则输出最短时间。

样例验证

输入 #1

1
2 1
3

M = 2^1 = 2，质因数只有 2。细胞 S=3 不包含质因数 2，因此无法满足要求。输出 -1。

输入 #2

2
24 1
30 12

m1=24, m2=1，所以 M=24。24 的质因数分解为 2^3 * 3^1。

• 对于细胞 30：30 = 2*3*5。对于质因数 2，需要 3/1=3 秒；对于质因数 3，需要 1/1=1 秒。所以需要 3 秒。
• 对于细胞 12：12 = 2^2 * 3。对于质因数 2，需要 ceil(3/2)=2 秒；对于质因数 3，需要 ceil(1/1)=1 秒。所以需要 2 秒。
  最终答案为 2。

复杂度分析

• 时间复杂度：对每个细胞 S，需要检查 factor_cnt 个质因数，每个质因数检查需要 O(log S) 的时间。总体复杂度约为 O(N * factor_cnt * log S)，在题目数据范围内可以接受。
• 空间复杂度：主要消耗是存储 m1 的质因数分解结果，空间复杂度为 O(factor_cnt)。

这个解法避免了直接计算巨大的 M，而是通过质因数分解将问题转化为指数比较，从而高效求解。

---

蒜鸟蒜鸟，睡了