Acwing-基础算法课笔记之数学知识（快速幂）

一、快速幂

1、引入

求 $a^b\%c$ 的值，其中$a$，$b$，$c$是整数，且$0<a$，$c<10^9$，$0<b<10^{18}$。

$\bullet$首先想到的最朴素的算法是，考虑用循环直接计算$a^b$的值，最后将其对$c$取模。

代码如下：

long long ans = 1;
for(long long i = 1; i <= b; i++){
    ans *= a;
}
ans %= c;
1
2
3
4
5

那么这个算法是有一定缺陷的，它的时间复杂度为$O(b)$，并且远远超过了数据类型$long$ $long$的范围。

$\bullet$取模运算的性质
例如：$(a\cdot b)\%p=[(a\%p)\cdot (b\%p)]\%p$

证明：设 { a = k 1 p + q 1 b = k 2 p + q 2

$$\begin{cases} a=k_1p+q_1 \\ b=k_2p+q_2 \end{cases}$$ {a=k1​p+q1​b=k2​p+q2​​，其中 $k_1$和 $k_2$是商数，$q_1$和 $q_2$是余数。

$(a\cdot b)=(k_{1}p+q_1)\cdot (k_{2}p+q_2)$

$=(k_1\cdot k_2\cdot p+k_1\cdot q_2+k_2\cdot q_1)\cdot p+q_1\cdot q_2$

所以 $(a\cdot b)\%p=(q_1\cdot q_2)\%p$

所以 $a\%p=q_1$，$b\%p=q_2$。

再例如，$(a\cdot a\cdot \cdot \cdot \cdot \cdot a)\%p$，每乘一次对 $p$取模，$ans=ans\times a$，$ans=ans\%c$，通过这种方式可以防止超过 $long$ $long$的范围，但还是用了 $b$次循环，时间复杂度还是 $O(b)$。

$\bullet$考虑手算 $3^{10}$，证明如下：

$3^{10}=(3^2{)}^5=9^5=9\times 9^4=9\times (81{)}^2=9\times (81^2{)}^1$

当指数是偶数时，我们可以将指数除以 $2$ 底数平方，当指数是奇数时，先将 $ans$ 乘以底数，再将底数平方，指数整除 $2$。

由上可知，$b$ 每次都要整除 $2$，即 $b=2^n$，所以执行的次数是$n$次，时间复杂度是$O(lo{g}_{2}b)$。

2、代码模板

ll faster_power(ll a, ll b, ll c) {
	ll ans = 1;
	a %= c;
	while (b) {
		if (b & 1) {
			ans = (ans * a) % c;
		}
		a = (a * a) % c;
		b >>= 1;
	}
	return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12

二、乘法逆元

1、乘法逆元的定义

若整数 $b$，$m$互质，并且对于任意的整数 $a$，如果满足 $b\%a=0$，则存在一个整数 $x$，使得 $\frac{a}{b}\equiv a\times x(mod$ $m)$，则称 $x$ 为 $b$ 的模 $m$ 乘法逆元，记为 $x=b^{-1}$然后有$bx\equiv 1(mod$ $m)$引入乘法逆元，就是为了解决模意义下的除法问题。

$b$ 存在乘法逆元的充要条件是 $b$ 与模数 $m$ 互质，即 $gcd(b,m)=1$

由以上可知：

$\frac{a}{b}\equiv a\times x(mod$ $m)$

$\iff$$\frac{a}{b}\equiv a\times b^{-1}(mod$ $m)$

$\iff$$b\times \frac{a}{b}\equiv b\times a\times b^{-1}$

$\iff$$a\equiv a\times b\times b^{-1}$

$\iff$$b\times b^{-1}\equiv 1(mod$ $m)$

2、费马定理

在数论中，假如 $a$ 是一个整数，$p$ 是一个质数

$a^p\equiv a(mod$ $p)$

如果$a$不是$p$的倍数

$a^{p-1}\equiv 1(mod$ $p)$

例如：设$a=3$，$p=5$，则有：

$3^{5-1}=3^4=81mod$ $5=1$

设 $p$ 为质数，依据上面的结论得：

$b\times x\equiv 1(mod$ $p)$

$\iff$$b^{p-1}\equiv 1(mod$ $p)$

$\iff$$b\times b^{p-2}\equiv 1(mod$ $p)$

$\iff$$a^{p-2}(mod$ $p)$