P4348 幂的末尾（【基础】）

解题思路

$7^{2011}$ 是一个天文数字，直接算根本存不下。但我们只需要末三位，而乘法有个好性质：两个数相乘的末三位，只和这两个数的末三位有关。所以每乘完一次立刻对 1000 取模，只保留末三位，继续乘下去结果不变。这就是"边乘边取模"。

循环 $b$ 次，每次 r = r * a % 1000 就行。但这里有个细节：如果幂本身不到三位，比如 $2^3=8$，要输出 8 而不是 008；如果幂超过三位但末三位以 0 开头，比如 $2^{10}=1024$，末三位是 024，要补前导 0 输出 024。

所以用一个标记 big 记录"幂是否已经达到三位数以上"：只要某次乘完的结果达到或超过 1000，就说明真正的幂已经超过三位，把 big 记成 true。最后输出时，如果 big 为真，就按三位补齐前导 0；否则直接输出整数本身。

拿样例 $7^{2011}$ 验证：边乘边取模，最后得到的末三位是 743，和样例一致。

边界情况：底数 $a=1$ 时，不管指数多大，幂都是 1，程序输出 1；底数 $a=100$、指数 $b=1$ 时，幂是 100，超过三位要输出 100，都能正确处理。

参考代码

// 计算a的b次方的末三位数字
#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    int r = 1;          // 记录末三位
    bool big = false;   // 幂是否已经达到三位数以上
    for (int i = 0; i < b; i++) {
        r *= a;
        if (r >= 1000) {   // 超过三位，只保留末三位
            big = true;
            r %= 1000;
        }
    }
    if (big) {          // 幂超过三位，不足三位要补前导0
        if (r < 100) cout << 0;
        if (r < 10) cout << 0;
    }
    cout << r << endl;
    return 0;
}

复杂度分析

循环 $b$ 次，$b$ 最大 10000，每次只做乘法和取模，所以时间复杂度是 $O(b)$，运行飞快。只用了两个整数和一个布尔变量，额外空间复杂度是 $O(1)$。