Note - 快速幂和矩阵乘法

Part1. 快速幂（写给CTR）

问题：给定 $a,b,p$ ，求出 $a^b\mod p$ 。

对于这个问题，有一个显然的解法：将答案初始化为 $1$ ，我们循环 $b$ 次，每次都将答案乘上 $a$ ，并模个 $p$ 。显然地，此方法时间复杂度为 $O(b)$ 。

代码 $cpp$ :

int s=1;
for (int i=1;i<=b;++i) s=(long long)s*a%p;
cout<<s;

代码 $py$ ：

s=1
for i in range(0,b) s=s*a%p
print(s)

当然 $python$ 自带的 $a**b$ 是可以在 $O(\log n)$ 的时间内解决这个问题的，只是 $a,b$ 大的时候会有点慢。

不过我们视此为作弊，不讨论。

我们来寻找优化方法。

首先，我们来介绍一下新角色：二进制。

我们平时写数，以及电脑给我们呈现的，大多都是十进制的。

我们知道，一个数在十进制表示下的规则是满十进一，每一位上的数都是 $0...9$ 中的一个。

我们板板手指头想想，发现如果一个正整数只有一位不为零，从右往左数第 $i$ 位是 $j$ 的话，那么这个数就是 $j\times {10}^i$ 。

每个十进制数都可以拆分成若干个如上所说的数。比如

$$6012 = 6000 + 10 + 2 = 6\times{10}^3 + 1\times{10}^1 + 2\times{10}^0$$

但这样拆分好像非常复杂，没个鸟屎用。

这个时候，二进制就出场了。

类比十进制，二进制是满二进一，每一位上的数不是 $0$ 就是 $1$ 。

可见，二进制要简洁的多，所以计算机运算都是使用二进制的。

类比一下，发现如果一个正整数（二进制表示）只有一位不为零，从右往左数第 $i$ 位是 $1$ 的话，那么这个数就是 $2^i$ 。

这个比十进制简洁多了。我们不妨用 $(x)_2$ 表示 $x$ 是一个二进制表示。

那么每个二进制数都能拆分，比如

$$(1011)_2 = (1000)_2 + (10)_2 + (1)_2 = 2^3 + 2^1 + 2^0$$

而一个数 $x$ 最多能拆成几个 $2^n$ 呢？很显然是 $O(\log x)$ 的。

于是我们可以将瓶颈 $b$ 进行拆分，那么答案 $a^b\mod p$ 就是

$$a^b = a^{\sum_{i=1}^{k} B_i} = \prod_{i=1}^{k} a^{B_i}$$

其中

$$b = \sum_{i=1}^{k} B_i, \forall i\in [1,k], B_i = 2^{r_i} ,\forall j\in [1,k], i\neq j,r_i\neq r_j$$

显然 $k< \log_2 b, r_i\leq \log_2 b$ ，那我们只需要知道 $a^{2^0}, a^{2^1}, ..., a^{2^{\lfloor\log_2 b\rfloor}}$ 就行了。

很容易发现 $a^{2^i} = (a^{2^i})^2, a^{2^0} = a$ 。那就可以在 $O(\log b)$ 内求 $a^{B_i}$ 了，连乘，由于 $k<\log_2 b$ ，也可以在 $O(\log b)$ 内求出。

总复杂度 $O(\log b)$ 。

代码 $cpp$ ：

int s=1;
while (b){
	if (b&1) s=(long long)s*a%p;
	a=(long long)a*a%p;
	b>>=1;
}
cout<<s;

代码 $py$ ：

print("Tell me a and b, I will output the last four numbers of a^b!\n")
print("I can tell you the answer in O(log b) time!\n")
a = int(input("a = ?\n")) # 输入
b = int(input("b = ?\n"))
aa = a # 赋值，便于输出时使用
bb = b
p = 10000 # p是模数
s = 1 # s是当前答案
# 接下来的注释假设循环了q次
while b > 0:
    if b % 2 == 1: # 如果b的二进制表示下最后一位是1，也就是我们需要计算a^(2^q)
        s = s * a % p # 那就将答案乘上a（现在的a已经是a^(2^q)了）
    a = a * a % p # a是不断平方的，循环q次，a就是原先的a^(2^q)
    b = b//2 # b将二进制表示下最后一位删去
print("The last four numbers of ",aa,"^",bb," is ",s%p) # 输出