本文旨在以浅显易懂的方式让读者学会快速幂求余。

数学原理#

公式1

$a^b\ mod\ c = (a\ mod\ c)^b$

公式2

$(a*b)\ mod\ c = [(a\ mod\ c)*(b\ mod\ c)]\ mod\ c$

分步实现#

首先，我们对某一个值求幂,比如 $a^b$ ，就相当于一个b个a的乘积。

先来个简单的实现。

fn mypow(a: usize, b: usize) -> usize {
    let mut result = 1;
    let mut b = b;
    while b > 0 {
        result *= a;
        b -= 1;
    }
    result
}

想象一下这里有一排等待被你处理的a。

a a a a a a a a … a

哎，我们数了一下，发现刚好可以分成两队(b%2==0)

a a a a … a

a a a a … a

两队站开之后让他们上下在一起。

$a^2\ a^2\ ...\ a^2$

如果没有数字偷跑，那么现在应该剩下 $\frac{b}{2}$ 对新人

假如分出两队多出了一个老六，那就让他单独站在旁边。

写一个简单的代码

fn mypow(a: usize, b: usize) -> usize {
    let mut result = 1;
    let mut a = a;
    let mut b = b;
    while b > 0 {
        if b % 2 == 1 {
            result *= a;
            // 先把老六先清算掉
        }
        // 剩下的可以继续两两结合
        a = a.pow(2);
        b /= 2;
    }
    result
}

刚接触的时候我还很疑惑，怎么只有b为奇数的时候计算result,偶数却不算。 这里提一嘴，我们只计算老六，可以结合的优先结合，等最后再算。

现在我们再来回顾一下这个公式:

$a^b\ mod\ c = (a\ mod\ c)^b$

然后观察一下我们上面的代码，用公式替换掉。

fn mypow(a: usize, b: usize, c: usize) -> usize {
    let mut result = 1;
    let mut a = a % c;
    // 这里可以直接先处理一下a
    // 完全符合公式1的替换条件
    // 我们把 (a mod c) 作为新的a绑定
    let mut b = b;
    while b > 0 {
        if b % 2 == 1 {
            result = (result * a) % c;
            // 先把老六先清算掉
            // 这里也可以求个余
        }
        // 剩下的可以继续两两结合
        a = a.pow(2) % c;
        // 出现了pow，用公式1
        b /= 2;
    }
    result
}

总结#

其实理解下来记忆，其实也不难。 就是把计算乘积的过程优化了。 本来我们应该计算b次，但是我们一直在增大a的同时减小最后计算乘积的次数。

就好比现在有5个小笼包站成一排，我们的目标是全部都吃下肚。一开始我们会选择拿5次，吃5次。现在我们先两两组合，变成2 2 1，我们把1吃掉,剩下2 2。再次结合4，我们只吃了两次就吃完了。(只是为了方便理解，实际上我们分组的过程也是会消耗时间，即分组过程也进行了乘积计算。)