简要题意：

求 $a^b \space \text{mod} \space p$ 的值。$a,b,p \leq 10^9$.

算法一

考虑 $a,b,p \leq 10^7$ 怎么做。

根据乘方的意义可得：

$$a^b = a \times a \times \cdots a (b \text{个} a \text{相乘})$$

这样我们可以用 $\mathcal{O}(b)$ 的时间完成本题。

伪码如下：

for(i=1;i<=b;i++) s=(s*a)%p
print(s)

算法二

考虑如何做 $a,b,p \leq 10^9$.

我们的瓶颈在于快速计算 $a^b$. 你会发现：

$a^b = (a^2)^{\frac{2}{b}} , \space \space \space \space \space \space \space \space b \equiv 0 \pmod 2$
$a^b = (a^2)^{\lfloor \frac{2}{b} \rfloor} * a, b \equiv 1 \pmod 2$

这样的话，每次 $b \gets b \div 2$，可以在 $\mathcal{O}(\log b)$ 的时间内解决问题。

伪码如下：

while(b) {
    if(b&1) ans=(ans*a)%p
    a=(a*a)%p b>>=1;
}

这是快速幂的经典问题，可以作为模板实现。