数学

要求 $n^k$ 的前三位和后三位，后三位的值可以使用模 $10^3$ 的快速幂计算。

前三位的值可以对 $n^k$ 换底得到 $n^k = 10^{\lg n^{k}} = (10^{\lg n})^k = 10^{k \lg n}$，观察到指数 $k \lg n$ 的整数部分控制 $n^k$ 的位数，小数部分控制 $n^k$ 各个位上数字的值。

使用 $\{ k \lg n \}$ 表示 $k \lg n$ 的小数部分，容易得到 $1 \leq 10^{\{ k \lg n \}} < 10$，所以 $n^k$ 的前三位就是 $\left\lfloor 100 \times 10^{\{ k \lg n \}} \right\rfloor$。可以直接使用 log10 函数求常用对数的值。

时间复杂度 $O(\log k)$。