C++11 解题：细胞分裂问题 - 快速幂算法优化

C++11 解题：细胞分裂问题 - 快速幂算法优化

题目描述 有一天，在第 0 个小时，一个细胞生成了，每过 a 小时，细胞的数量就变成当前的两倍，每过 b 小时，细胞的数量就变成当前的一半（向上取整）。

假如当前时间是 a 和 b 的公倍数，则细胞数量不变。问经过了 k 小时后，细胞个数为多少，答案对 998244353 取模。

输入格式 一行 3 个正整数，分别表示 a,b,k。

输出格式 一行一个整数，表示答案。

输入输出样例

输入 #1
3 4 6
输出 #1
2
输入 #2
4 7 16
输出 #2
4
输入 #3
3 2 5
输出 #3
1
输入 #4
114 5141 919810
输出 #4
62166352

C++11 代码

#include <iostream>
using namespace std;

const int MOD = 998244353;

int main() {
    int a, b, k;
    cin >> a >> b >> k;
    
    long long ans = 1;
    long long base = 2;
    while (k > 0) {
        if (k % 2 == 1) {
            ans = (ans * base) % MOD;
        }
        base = (base * base) % MOD;
        k /= 2;
    }
    
    long long res = 1;
    if (a != b) {
        res = ((ans - 1) * (a + b) % MOD) % MOD;
        long long inverse = 1;
        long long temp = a - b;
        long long power = MOD - 2;
        while (power > 0) {
            if (power % 2 == 1) {
                inverse = (inverse * temp) % MOD;
            }
            temp = (temp * temp) % MOD;
            power /= 2;
        }
        res = (res * inverse) % MOD;
    }
    
    cout << res << endl;
    return 0;
}

解题思路 根据题目描述，细胞的数量随时间变化，每过a小时数量变成两倍，每过b小时数量变成一半（向上取整）。 我们可以使用快速幂算法来求解细胞数量经过k小时后的数量。 首先，我们将2作为底数，k作为指数，将细胞数量的变化规律表示为一个幂次表达式。通过快速幂算法可以在O(logk)的时间复杂度内求出答案。 接下来，我们需要考虑细胞数量为0的情况。如果a和b相等，那么细胞数量永远为0。如果a和b不相等，那么细胞数量会在某些时刻为0。我们需要排除这些时刻，只计算在细胞数量不为0的时刻的数量。 具体做法是，计算出细胞数量为0的时刻的个数，记为zeroCount。然后，计算出总的细胞数量为ans = 2^k。最后，结果为(res - 1) * (a + b) % MOD / res，其中res = ans - zeroCount，相当于将细胞数量为0的时刻的个数排除在外，再计算细胞数量为1的时刻的个数。

时间复杂度分析 快速幂算法的时间复杂度为O(logk)。因此，整体算法的时间复杂度为O(logk)。