class="markdown_views prism-atom-one-light"> 快速幂也就是我们求解ab mod k" role="presentation">ab mod k$a^{b}modk$这种类型的式子会用

1. 解法一 暴力求解

暴力求解也就是类似下面代码

for(int i = 0;i {
a *=a;
}
a%=k;

这种方法是不可取的
例如：
21003% 3" role="presentation">21003% 3$2^{1003}\mathrm{\%}3$ 是非常消耗我们的计算资源的。
- - 缺点1：在我们在之后计算指数的过程中，计算的数字不都拿得增大，非常的占用我们的计算资源（主要是时间，还有空间）
- - 缺点2：我们计算的中间过程数字大的恐怖，我们现有的计算机是没有办法记录这么长的数据的，所以说我们必须要想一个更加高效的方法来解决这个问题

2. 解法二 引入 取模运算

在引入快速幂之前我们先了解一下取模运算 (a∗b)% k==(a% k)(b% k)% k" role="presentation">(a∗b)% k==(a% k)(b% k)% k$(a\ast b)\mathrm{\%}k==(a\mathrm{\%}k)(b\mathrm{\%}k)\mathrm{\%}k$
证明
①x=a∗m+b" role="presentation">x=a∗m+b$x=a\ast m+b$
②y=c∗m+d" role="presentation">y=c∗m+d$y=c\ast m+d$
③xy=(a∗m+b)(c∗m+d)=(a∗c∗m)2+(a∗d+b∗c)∗m+b∗d=b∗d(modm)" role="presentation">xy=(a∗m+b)(c∗m+d)=(a∗c∗m)2+(a∗d+b∗c)∗m+b∗d=b∗d(modm)$xy=(a\ast m+b)(c\ast m+d)=(a\ast c\ast m{)}^2+(a\ast d+b\ast c)\ast m+b\ast d=b\ast d(modm)$
则x=b mod my=d mod m" role="presentation">x=b mod my=d mod m$$\begin{gathered} x=bmodm \\ y=dmodm \end{gathered}$$ 得解(a∗b)% k==(a% k)(b% k)% k" role="presentation">(a∗b)% k==(a% k)(b% k)% k$(a\ast b)\mathrm{\%}k==(a\mathrm{\%}k)(b\mathrm{\%}k)\mathrm{\%}k$ 然后 我们的式子就可以变成 (2 mod 3)1003 mod 3" role="presentation">(2 mod 3)1003 mod 3$(2mod3{)}^{1003}mod3$ 这时我们的代码可以变成 int i = (a%k); //i代表我们每次运算时要乘的数字 for(;b>1;b--){ a%=k; //a取模 a=a*i; } a%=k; 但这样还不够，当我们b足够大时，我们要进行b次实验。这样还是会浪费许多时间

3. 解法三 引入幂运算的取模运算

前面引入了取模运算在这里我们再来讲一下 一种新的幂运算
ab=(a2)b2" role="presentation">ab=(a2)b2$a^b=(a^2{)}^{\frac{b}{2}}$
由这个公式可以把我们的运算变成了b2" role="presentation">b2$\frac{b}{2}$次。
比如21000000072100000089mod 45987" role="presentation">21000000072100000089mod 45987${2100000007}^{2100000089}mod45987$ 这样用上面的方式运算时肯定要超时的。 我们就可以用这个
步骤如下：
①先判断b能否被整除
因为我们的的最终结果将在 B2==1" role="presentation">B2==1$\frac{B}{2}==1$时出结果
若不能整除 我们的res=a∗res%k" role="presentation">res=a∗res%k$res=a\ast res\mathrm{\%}k$ 一方面使我们的b始终为偶数，一方面也记录了我们的答案
②计算 a2%k" role="presentation">a2%k$a^2\mathrm{\%}k$
代码如下 long res = 1; for(;b>1;b/=2){ if(b/2==1) { res = res*a%k; } a=(a*a)%k; } 例题：