禽兽的传染病(Beast Epidemic) 题解

思路分析

设第 $i$ 轮后的患病总数为 $f_i$，初始 $f_0 = 1$；每轮新增 $f_{i-1} \times x$ 只，故 $f_i = f_{i-1} \times (x + 1)$，即 $(x + 1)^n$。注意题目说明答案在 $64$ 位无符号整数范围内，必须使用 unsigned long long 累乘 $n$ 次。时间复杂度 $O(n)$ 或 $O(\log n)$。

参考代码

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    unsigned long long x, n;
    if (!(cin >> x >> n)) return 0;
    unsigned long long ans = 1, base = x + 1;
    while (n > 0)
    {
        if (n & 1ULL) ans *= base;
        n >>= 1ULL;
        if (n > 0) base *= base;
    }
    cout << ans << "\n";
    return 0;
}