【数论】—— 快速幂与扩展欧拉定理

快速幂与扩展欧拉定理

把这两个知识点放一起是因为扩展欧拉定理需要用到快速幂。

快速幂

定义

快速幂，即很快的做幂运算，并且在求幂的同时支持取模操作。但这个算法究竟是怎么实现的，我们来探究一下。

快速幂的原理

假设我们需要求 $2^8$ 是多少？

最暴力的方法就是一个一个乘：

$$\underset{8个2}{\underbrace{2\times 2\times \cdots \times 2\times 2}}=256$$

这样的时间复杂度是：$O(n)$。当指数大时，这样的暴力一定 T 到飞起。

当然，聪明的你们（不是我）一定发现了一个简便的方法，那就是让底数不断平方，然后指数不断除以 $2$。即：

$$2^8=2^{2^4}=4^4=4^{2^2}=16^2=256$$

不难发现，这样求幂只运算了 $3$ 次，是 $\log$ 级别的。但如果指数不是 $2$ 的倍数怎么办呢？我们再来看一个例子：

求 $2^{10}$ 是多少？

我们还是先按之前的方法做：

$$2^{10}=2^{2^5}=4^5$$

现在我们发现指数变成了奇数，不能再除以 $2$ 了。对于这种情况，我们可以这样处理：把一个底数单独拿出来，使得指数减一而成为偶数。即：

$$4^5=4^4\times 4$$

经过处理，我们就可以继续重复原来的步骤了：

$$4^4\times 4=16^2\times 4=256\times 4=1024$$

这两个步骤就是快速幂算法的主要流程。

具体实现：

我们可以定义变量 result，记得一定要初始化为 $1$。然后如果指数变成了奇数，则令result乘上底数，否则指数除以二，底数平方。

代码实现

由上面的两个步骤，我们可以写出基本的算法框架：

int ksm(int base , int x) {
	int result = 1;
	while(x) {
		if(x % 2 == 1)
			result *= base;
		x /= 2;
		base *= base;
	}
	return result;
}

但这还不是最快的算法。我们可以将取模运算以及除法运算改成位运算：

inline int ksm(int base , int x) {
	int result = 1;
	while(x) {
		if(x & 1)
			result *= base;
		x >>= 1;
		base *= base;
	}
	return;
}

欧拉定理与扩展欧拉定理

欧拉定理

定义

对于 $a$，$m$ 两数，若 $\gcd (a,m)=1$ 则有：$a^{\phi (m)}\equiv 1(\mathrm{mod}m)$。

其实费马小定理就是欧拉定理的特殊情况，即当 $m$ 为素数时。

欧拉定理的证明

设 $A=\left\{x_1,x_2,\cdots ,x_{\phi (m)}\right\}$ 是 $1-m$ 中与 $m$ 互素的数的集合。

则这些数模 $m$ 互不相同，且余数与 $m$ 互素。

接下来，我们来证明集合 $B=\left\{a{x}_1,a{x}_2,\cdots ,a{x}_{\phi (m)}\right\}$ 且 $\gcd (a,m)=1$ 也有这样的性质。

我们先证这些数模 $m$ 互不相同：

考虑反证法：

若 $a{x}_i\equiv a{x}_j(\mathrm{mod}m)$ 且 $i\ne j$。

则有 $a{x}_i-a{x}_j\equiv 0(\mathrm{mod}m)$。

即 $a(x_i-x_j)\equiv 0(\mathrm{mod}m)$。

因为 $a$ 与 $m$ 互素且 $x_i-x_j\nmid m$ 所以这种情况不存在，得证。

接下来，我们证余数与 $m$ 互素：

因为 $a$ 与 $m$ 互素，且 $x_i$ 与 $m$ 互素。

所以 $a{x}_i$ 与 $m$ 互素。得证。

所以 $B$ 集合在模 $m$ 后便于 $A$ 集合相等。可得：

$$\prod _{i=1}^{\phi (m)}a{x}_i\equiv \prod _{i=1}^{\phi (m)}{x}_i(\mathrm{mod}m)$$

把 $a$ 提出得：

$$a^{\phi (m)}\prod _{i=1}^{\phi (m)}{x}_i\equiv \prod _{i=1}^{\phi (m)}{x}_i(\mathrm{mod}m)$$

同时约掉 ${\prod }_{i=1}^{\phi (m)}{x}_i$ 得：

$$a^{\phi (m)}\equiv 1(\mathrm{mod}m)$$

得证。

欧拉定理的推论与证明

若 $a$，$m$ 互素，则有 $a^b\equiv a^{b\mathrm{mod}\phi (m)}(\mathrm{mod}m)$。

下面给出证明：

设 $b=k\times \phi (m)+t$，其中 $t=b\mathrm{mod}\phi (m)$。

把 $b$ 代入 $a^b$ 得：

$$\begin{array}{rl}{a}^b& =a^{k\times \phi (m)+t}\\ & =a^{k\times \phi (m)}\times a^t\\ & =a^{\phi (m{)}^k}\times a^t\\ & \equiv 1^k\times a^{b\mathrm{mod}\phi (m)}(\mathrm{mod}m)\\ & \equiv a^{b\mathrm{mod}\phi (m)}(\mathrm{mod}m)\end{array}$$

得证。

扩展欧拉定理

在大部分情况下，我们都使用扩展欧拉定理，因为它可以处理的情况更多。

定义

对于 $a^b\mathrm{mod}m$ 这样一个式子，无论 $a$ 与 $m$ 互不互素都有：

$$a^b\mathrm{mod}m\equiv \{\begin{array}{l}b\ge \phi (m),a^{b\mathrm{mod}\phi (m)+\phi (m)}(\mathrm{mod}m)\\ b<\phi (m),a^b(\mathrm{mod}m)\end{array}$$

• 对于第一种情况，即 $b\ge \phi (m)$ 时我们可以用公式化简来求解。

• 对于第二种情况，我们可以直接使用快速幂算出结果。

算法流程十分简单，我们只需要判断 $b$ 与 $\phi (m)$ 的大小，然后按照对应的公式计算即可。

代码

inline int phi(int x) {
	int ans = x;
	for(register int i = 2;i <= sqrt(x);i ++)
		if(x % i == 0) {
			ans = ans / i * (i - 1);
			while(x % i == 0)
				x /= i;
		}
	if(x > 0)
		ans = ans / x * (x - 1);
	return ans;
}

inline int ksm(int base , int x , int m) {
	int result = 1;
	while(x) {
		if(x & 1)
			result = result * base % m;
		x >>= 1;
		base = base * base % m;
	}
	return result;
}

inline int solve(int a , int b , int m) {
	int phi_m = phi(m);
	if(b >= phi_m)
		return ksm(a , b % phi_m + phi_m , m);
	else
		return ksm(a , b , m);
}

证明不放了，以后再 update 吧。