快速幂(卡速米)

# 快速幂 ### 什么是快速幂 顾名思义，快速幂就是跑得特别快的算一个数几次方的的运算。 ### 朴素算法 求$a^n$的值 ```cpp for (int i = 1; i <= n; i++) { res *= a; } ``` 显然，复杂度是O($n$)的，这显然不是十分快速的算法。 ### 利用cmath库 ```cpp res = pow(a, b); ``` 告诉你，实际上它的复杂度也不是很健康，~~可能不如你的朴素算法快~~。 ### 快速幂 #### 快速幂的速度到底有都快呢 求$a^n$的值，只需要O($logn$)的时间。 #### 快速幂是如何实现的呢 求$a^n$的值，我们思考一个问题。 如果$n$是一个偶数： $a^n$ = $a \times a \times a ... \times a$ ($n$个$a$) = $a^2 \times a^2 \times ... \times a^2 $($n /2$个$a^2$) 如果$n$是一个奇数 ： $a^n$ = $a^{n-1} \times a$，之后就转化成了偶数的问题。 这样，我们不难发现，每进行一次偶数操作，$n$的值都会变为原来的一半，这样，我们就可以在O($logn$)的时间内求出$a^n$的值了。 递归代码：(求$a^n$) ```cpp int Kasumi(int n) { if (n == 0) { return 1; } int res = Kasumi(n / 2); res = res * res; if (n % 2 == 1) { res *= a; } return res; } ``` 非递归代码：(求$a^n$) ```cpp int Kasumi(int n) { int res = 1, base = a; while (n) { if (b % 2 == 1) { ans *= base; } base *= base; b /= 2; } return res; } ``` ## 如果需要取膜呢？ ### 前提知识储备 $ a \times b $ % $c$ = ($ a $ % $ c $) $\times$ ($b$ % $c$) % $c$ ### 然后就没什么了 递归代码：(求$a^n$ % $mod$) ```cpp int Kasumi(int n) { if (n == 0) { return 1; } int res = Kasumi(n / 2); res = res * res % mod; if (n % 2 == 1) { res = (res * a) % mod; } return res; } ``` 非递归代码：(求$a^n$ % $mod$) ```cpp int Kasumi(int n) { int res = 1, base = a; while (n) { if (b % 2 == 1) { ans = (ans * base) % mod; } base = (base * base) % mod; b /= 2; } return res; } ```