【基础算法】倍增

倍增思想

倍增，顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理，极大地优化时间复杂度。

---

一. 快速幂算法

1. 什么是快速幂

• level 1

  当我们要计算 $a^{64}$ 时，我们可以一个一个算的方式即：$a\times a\times \cdots a$，这样算 64 次即可得出答案，但是当数很大时，我们这个做法显然是会超时的。

• level 2

  于是，我们可以利用幂运算的性质，即：

$$\begin{gathered} a^1\times a^1=a^2 \\ {a}^2\times a^2=a^4 \\ ⋮ \\ {a}^{32}\times a^{32}=a^{64} \end{gathered}$$

​ 这样的话，我们只需要算 6 次就可以快速得到结果了，我们通过一个翻倍的过程，将时间复杂度直接从 $O(n)$ 优化到了 $O(\log N)$。

• level 3

  但是，$a^{64}$ 这个例子有点特殊了，我们发现它的指数，也就是 $a^n$ 中的 $n$，恰好是 2 的幂。那如果不是呢？比如 $a^{105}$。
  注意到，虽然 105 不是 2 的幂，但是它可以拆解成几个 2 的幂的和的形式：
  $$105=1+8+32+64$$
  于是，通过指数运算的性质，我们有：
  $$\begin{array}{rl}{a}^{105}& =a^{1+8+32+64}\\ & =a^1\times a^8\times a^{32}\times a^{64}\end{array}$$

  这样的话，我们就可以利用 level 2 中计算出的结果来求出 $a^{105}$ 了，那么我们是如何得到 $105=1+8+32+64$ 的呢？

• level 4

  这时候就要用到我们的二进制了，我们高中的时候都学过一个数表示成二进制的转换方法。例如：二进制数 1011，它的值在 10 进制中可以表示为 $1\times 2^0+1\times 2^1+0\times 2^2+1\times 2^3$，也就是 11。

  通过这个转换方法，我们就可以把 $a$ 的指数 $n$ 转换成为 $2^k$ 的序列之和的形式。具体这个 $2^k$ 是乘 0 还是乘 1，这就看对应的二进制位上是 0 还是 1 了。

以上的过程就是倍增思想中的快速幂算法。

---

2. 模运算的性质与技巧

上面的快速幂算法从时间上解决了计算某一个数的某次方的过程，但是如果的底数和指数都非常大，最终结果连 long long 都存不下的时候，我们往往会对结果进行取模，也就是通常题目会让你计算 $a^b\mathrm{mod}p$ 的结果。 但是我们在计算 $a^b$ 的过程中就有可能超出存储范围，这个时候我们不能等到算完再取模，而是要在算的过程中边算边取模。下面介绍模运算的几个性质：

（1）当计算过程中只有 “加法” 和 “乘法” 的时候，取模可以放在任意的位置。

也就是说，如果我们计算
$$(a\times b\times c\times d)\mathrm{mod}p$$
时，它的结果等同于
$$(((((a\times b)\mathrm{mod}p)\times c)\mathrm{mod}p)\times d)\mathrm{mod}p$$
也等同于
$$((a\mathrm{mod}p)\times (b\mathrm{mod}p)\times (c\mathrm{mod}p)\times (d\mathrm{mod}p))\mathrm{mod}p$$
（2）当计算过程中存在减法时，结果可能是负数，此时如果需要补正则需要使用 “模加模” 的技巧。

也就是当我们计算
$$(a-b)\mathrm{mod}p$$
时，$b$ 有可能大于 $a$，此时结果是一个负数，那么我们可以对 $a-b$ 先模 $p$，再加上一个 $p$ 变成正数，再取模：
$$((a-b)\mathrm{mod}p+p)\mathrm{mod}p$$

---

3. 【模板】快速幂 ⭐

【题目链接】

P1226 【模板】快速幂 - 洛谷

【题目描述】

给你三个整数 $a,b,p$，求 $a^b\mathrm{mod}p$。

【输入格式】

输入只有一行三个整数，分别代表 $a,b,p$。

【输出格式】

输出一行一个字符串 a^b mod p=s，其中 $a,b,p$ 分别为题目给定的值， $s$ 为运算结果。

【示例一】

输入

2 10 9

输出

2^10 mod 9=7

【说明/提示】

样例解释

$2^{10}=1024$，$1024\mathrm{mod}9=7$。

数据规模与约定

对于 $100\%$ 的数据，保证 $0\le a,b<2^{31}$，$a+b>0$，$2\le p<2^{31}$。

#include<iostream>using namespace std;typedef long long LL;LL a, b, p;// 快速幂模板
LL q_pow(LL a, LL b, LL p)
{LL res = 1;while(b){// 如果指数对应的二进制的当前位为 1if(b & 1) res = res * a % p;a = a * a % p;b >>= 1;}return res;
}int main()
{cin >> a >> b >> p;printf("%lld^%lld mod %lld=%lld", a, b, p, q_pow(a, b, p));return 0;
}

---

二、六十四位整数乘法 ⭐

【题目链接】

P10446 64位整数乘法 - 洛谷

【题目描述】

求 $a$ 乘 $b$ 对 $p$ 取模的值。

【输入格式】

第一行输入整数 $a$，第二行输入整数 $b$，第三行输入整数 $p$。

【输出格式】

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

【示例一】

输入

3
4
5

输出

2

【说明/提示】

$1\le a,b,p\le 10^{18}$

---

1. 解题思路

这道题与快速幂算法思路几乎一样，$a\times b$ 本质上就是 $b$ 个 $a$ 相加。直接相乘或者先模再乘都是会溢出的，我们也不可能真的就写一个循环来循环 $b$ 次，这个时候就要用到倍增的思想。

一个数通过它的二进制可以表示成为多个 2 的幂相加的形式，比如
$$\begin{array}{rl}13\times 11& =13\times (1\times 2^0+1\times 2^1+0\times 2^2+1\times 2^3)\\ & =13\times 1+13\times 2+13\times 0+13\times 8\end{array}$$
那么这个本来需要循环 11 次的运算就变成了只需要 4 次，大大降低了时间复杂度。原理就是把 “累加次数” 不断加倍，这样计算的话，不但时间复杂度低，边计算边取模就不会溢出了。

---

2. 代码实现

#include<iostream>using namespace std;typedef long long LL;LL a, b, p;LL solve(LL a, LL b, LL p)
{LL res = 0;while(b){// 如果 b 对应的二进制当前位为 1if(b & 1) res = (res + a) % p;a = (a + a) % p;b >>= 1;}return res;
}int main()
{cin >> a >> b >> p;cout << solve(a, b, p) << endl;return 0;
}