简化版题意 多次询问$a^b\%p$的值，其实就是强化版的快速幂。

$30\%：$

裸的快速幂,复杂度$O(Tlogb)$

$50\%$~$70\%：$

发现对于$50\%$的数据，$b\le$$10^{30}$，普通的变量无法存储指数，加上一点儿简化的高精度即可，复杂度仍然为$O(Tlogb)$

（不过貌似造数据的时候有点水了，实际上高精度能够拿到$70pts$，并且考试的时候有人直接$Python$就拿了$70$）。

$100\%：$

发现数据范围非常独特，只有指数$b$非常之大，而底数$a$和模数$p$都与正常快速幂无异，因此本题应从如何处理指数$b$入手。

这里，我们就要用到一个重要的数论知识——费马小定理。其形式如下：

若$p$是质数，则对于任意整数$a$，有$a^p≡a(mod\ p)$

当$a$,$p$互质，且$p$为质数时，有$a^{p−1}≡1(mod\ p)$

利用这个公式，我们进行以下推导：

当$b>p$时，$a^b≡a^{b−p+1}(mod\ p)$，那么在进行多次恒等后，新的指数最终将会小于$p-1$

此时有恒等式$a^b≡a^{b\%(p−1)}(mod\ p)$成立

因此，我们将指数$b$以字符串形式读入，从最低位起依次叠加，乘$10$，模$p-1$，得到新的指数，再进行快速幂即可，复杂度$O(T(logp+lgb))$。