快速幂取模
现在让我们来计算\(a^b\%c\)
最简单的想法
将\(a\)累计乘上\(b\)次再对\(c\)取模即可
1 | long long pow(long long a, long long b, long long c) |
看上去没有问题,但是当\(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 | long long pow(long long a, long long b) |
非递归实现
1 | long long pow(long long a, long long b) |
取模
首先引入几个数学公式 \[ \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 | long long pow(long long a, long long b, long long c) |