【例29.2】 幂的末尾

解题思路

只保留乘积模 1000。每次乘 a 后立刻对 1000 取模，重复 b 次。最后按三位补零输出。

正确性说明

乘法取模与先乘出完整幂再取模等价，循环第 k 次后 ans=a^k mod 1000，最终就是末三位。

易错点

幂不足三位也要补零，例如 8 输出 008。

复杂度

时间 O(b)，空间 O(1)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a, b;
    cin >> a >> b;
    int ans = 1;
    for (int i = 0; i < b; i++)
        ans = ans * a % 1000;
    cout << setfill('0') << setw(3) << ans << "\n";
    return 0;
}