快速乘法

摘要: 本文介绍快速乘法的算法原理与代码模板

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

$$a^{11} = a^{2^{0}} \times a^{2^{1}} \times a^{2^{3}} \\ a \times 11 = a \times 2^{0} + a \times 2^{1} + a \times 2^{3}$$

在文章 快速幂 中我们了解了快速幂算法及其变种，在 矩阵快速幂及其动态规划优化中的应用 中我们了解了矩阵快速幂算法。

本文我们以一个模板题看一下快速乘法，与快速幂和矩阵快速幂这两个算法类似，也是有递归和二进制分解两种实现方式，但是应用相对少一些。

模板题

• 90. 64位整数乘法

求 a 乘 b 对 p 取模的值。

输入格式：
第一行输入整数a，第二行输入整数b，第三行输入整数p。

输出格式：
输出一个整数，表示 a*b mod p 的值。

数据范围：
1<=a,b,p<=1e18

输入样例：
3
4
5
输出样例：
2

算法：模下快速乘 递归

不求 $ab$ 而是求 $a\cdot\frac{b}{2}$, 然后先不求 $a\cdot\frac{b}{2}$, 而是先求 $a\cdot\frac{b}{4}$，…

对以上思路最直接的实现方式是递归, 代码如下:

代码 (C++)

ll quick_mul(ll a, ll b, ll MOD)
{
    if(a < b) 
        return quick_mul(b, a, MOD);
    if(b == 1) 
        return a % MOD;
    ll x = quick_mul(a, b >> 1, MOD);
    if(b & 1)
        return (x + x + a) % MOD;
    return (x + x) % MOD;
}

算法：模下快速乘 二进制分解

求 $ab \mod p$，其中 $1 \leq a,b,p \leq 10^{18}$。

解法类似快速幂的思想，将 b 二进制表示，即 $b = c_{k+1}2^{k-1} + … + c_{0}2^{0}$。其中 $c_{i} \in \{0, 1\}$。也就是将 b 表示为了 2 的幂次的和。

例如 $b=11$ 时，$b = 2^{0} + 2^{1} + 2^{3}$：

$$a \times 11 = a \times 2^{0} + a \times 2^{1} + a \times 2^{3}$$

若已经求出 $a \times 2^{i-1} \mod p$，则计算$a \times 2^{i} \mod p$ 时，每一步的结果都不超 $2 \times 10^{18}$。

代码 (C++，模板)

ll quick_mul(ll a, ll b, ll MOD)
{
    ll ans = 0;
    while(b)
    {
        if(b & 1) 
            ans = (ans + a) % MOD;
        a = (a + a) % MOD;
        b >>= 1;
    }
    return ans;
}

---

题目

• 29. 两数相除

题解看这篇文章 【分类讨论】力扣29-两数相除

---