快速幂取模

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

最简单的想法

\(a\)累计乘上\(b\)次再对\(c\)取模即可

1
2
3
4
5
6
7
8
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次,幂越大时,效果越明显。

递归实现

1
2
3
4
5
6
7
8
9
10
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;
}

非递归实现

1
2
3
4
5
6
7
8
9
10
11
12
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} \]

我们需要用到上面的第$( 3 ) $式,下面给出证明:

\[ \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 \]

最终结果

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
}