快速幂是用来解决$n^k \mod N$，将其时间复杂度从 $O(n)$ 减少到 $O(\log n)$ 。

原理

首先，了解一个模运算的概念

(a+b) mod N = (a mod N + b mod N) mod N

(a * b) mod N = (a mod N * b mod N) mod N

然后，对于一个数k，把它转换为二进制，

如11 = 1011

那么 $ n^{11} = n^8 * n^2 * n^1 $ 。

于是 $n^{11} \mod N = (n^8 \mod N) * (n^2 \mod N) * (n^1 \mod N)$

那么在循环过程中只需要一直记录$n^{2^m}$，每次判断$2^m$对应$k$的二进制位是$0$（不要）是$1$（要）就可以

代码

typedef long long ll;

ll quick_mod(ll n, ll k, ll N)
{
    ll num = 1, t = n;
    while (k) {
        if (k & 1)
            num = num * t % N;
        t = t * t % N;
        k >>= 1;
    }
    return num;
}

对于快速幂的扩展还有一个矩阵快速幂，它是对于矩阵做一个快速幂的处理，可以用于求斐波那契数列第n项模N

搬运自CSDN：https://blog.csdn.net/yueyue200830/article/details/85333813

Z Blog

算法学习（二）——快速幂

原理

代码