快速幂与快速幂取模

题目链接：https://ac.nowcoder.com/acm/contest/996/A

关于快速幂介绍：

• 问题引入：我们在处理a^b问题时，一般的做法就是连续乘上b次a，当b很大的时候，就会导致次数过多而超时的问题，而为了减少我们的计算次数，就研究出了快速幂算法。
• 理解：比如当我们需要计算2⁵时，一般做法即2*2*2*2*2，需要计算五次，而快速幂的思想就是2¹*2⁴，就只需要计算2次就好了，至于为什么是1和4呢，这就涉及到对5进行二进制处理，5₂=101，我们发现，为1的数位，我们就需要乘上去，这里有几个1我们就要计算几次，而基数的自己相乘是每一步都在进行的，不管当前是不是1.

代码实现：

ll pow(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1)   ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}

快速幂取模，就是在快速幂的基础上，运用数学公式a^b%p = (a % p)^{b % p} % p，进而获知快速幂取模的算法

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