快速幂取模

现在让我们来计算$a^b\%c$

最简单的想法

将$a$累计乘上$b$次再对$c$取模即可

long long pow(long long a, long long b, long long c)
{
    long long ans = 1;
    while (b--)
        ans = ans * a;
    ans = ans % c;
    return ans;
}

看上去没有问题，但是当$a$和$b$的值很大时，就算是long long类型也有可能让累乘的结果溢出，而且在做乘法时一共要进行$b$次运算，时间上的代价也很大，那么是否能从这两方面进行优化呢？

快速幂

快速幂是一个计算$a^b$的小技巧，它的时间复杂度为$\Theta \left( \log n \right)$，从一个简单的例子开始：

现在你要计算$62^9$这个数，假设你手上有个只能加减乘除的计算器，想必你肯定不会真的把$62$这个数乘上$9$次，因为这实在太慢了，我们会先计算$62^4$的值，将其与自身相乘后再乘上一个$62$就得到了结果，将这个规则递归下去，可以得到下面这样的流程

$$62^9=\left( 62^4 \right) ^2*62=\left( \left( 62^2 \right) ^2 \right) ^2*62$$

原本要进行9次乘法，现在只需要进行4次，幂越大时，效果越明显。

递归实现

long long pow(long long a, long long b)
{
    if (b == 0)
        return 1;
    long long ans = pow(a, b / 2);
    if (b & 1)
        return ans * ans * a;
    else
        return ans * ans;
}

非递归实现

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

取模

首先引入几个数学公式

\begin{align} \left( a+b \right) \%c &=\left[ \left( a\%c \right) +\left( b\%c \right) \right] \%c \tag{1} \\ \left( a-b \right) \%c &=\left[ \left( a\%c \right) -\left( b\%c \right) \right] \%c \tag{2} \\ \left( a*b \right) \%c &=\left[ \left( a\%c \right) *\left( b\%c \right) \right] \%c \tag{3} \end{align}

我们需要用到上面的第$\left( 3 \right) $式，下面给出证明：

\begin{align*} a\%c & =d\Rightarrow a=tc+d\\ b\%c & =e\Rightarrow b=kc+e\\ ab\%c & =\left( tc+d \right) \left( kc+e \right) \%c\\ & =\left( tkc^2+\left( te+dk \right) c+de \right) \%c\\ & =de\%c=\left[ \left( a\%c \right) *\left( b\%c \right) \right] \%c \end{align*}

根据这个公式，可以知道

$$a^b\%c=\left( a\%c \right) ^b\%c$$

最终结果

根据以上结论，我们可以在循环乘积的过程中加入取模运算，这样就可以避免最终结果过大的情况，再结合之前的快速幂技巧，就可以得到最终的代码

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