快速幂-逆元-取余公式

发表于 更新于 分类于
本文字数： 845 阅读时长 ≈ 3 分钟

取余公式

(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p ) % p
(a * b) % p = (a % p * b % p) % p

快速幂

利用倍增思想，当求解 a 的 b 次方时，代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
using namespace std;
using ll = long long;
ll quik_pow(ll a, ll b)
{
  //temp存放 a^1, a^2, a^3, a^4.......
	ll temp = a;
	ll ans = 1;
	while (b)
	{
    //判断b的二进制的最后一位是否为1，是1就算入总结果
		if (b & 1) ans = ans * temp;
    //随着b的二进制右移逐渐递变
		temp = temp * temp;
    //b的二进制右移（舍弃最后一位
		b >>= 1;
	}
	return ans;
}
int main()
{
	ll a, b;
  //输入a, b,求解a的b次方
	cin >> a >> b;
	ll ans = quik_pow(a, b);
	cout << ans << endl;
	return 0;
}

模板题 1，这题考察快速幂结合取余公式

模板题 2，这题要仿造快速幂，写出慢速积

逆元

什么是逆元？

在取余公式中，有+，-，*就是没有 除 /，就是因为除法不能直接满足取余公式。他得经过一个特殊的操作，就是求出除数的逆元。

例如 （5 / 5）mod 3 这个式子的答案显然是 1，先得出（5 / 5） = 1，再 1 mod 3 = 1
但是 当式子不能整除时 如：（12 / 5）mod 3 就得不出答案，于是有人规定一种方法，将除法转换为 乘于 原除数的逆元。这个规定不仅要能够解决（11 / 5）mod 3 得不出答案的情况，同时要满足（5 / 5）mod 3 的答案不变。

于是以上面两个分别作为例子。
（5 / 5）mod 3 —> （5 *（5 的逆元））mod 3 = 1（原来的答案）—> 不难看出 2 可以是 5 的逆元
同一个数在 mod 不同数时，它的逆元不一样；反之不变（这样也符合数学规律
（11 / 5）mod 3 —> （11 *（5 的逆元））mod 3 = （11 * 2）mod 3 = 1

这样我们就能大致明白逆元的定义了 但是我们思考，在求某个数的逆元时，是否有计算方法？难道全靠观察？如何让计算机帮我们计算逆元？

怎么求逆元

一.费马小定理：如果 p 是质数且 b 不是 p 的倍数，那么根据费马小定理：b^(p−1) ≡ 1 (mod p)

由此推出

b * b^(p−2) ≡ 1 (mod p)

因此 b ^ (p - 2) 是 b 的逆元

这样可以通过快速幂求出逆元

1
2
3
4
5
6
7
8
9
10
11
12
long long power(long long a, long long b)
{
    long long res = 1;
    a %= MOD;
    while (b > 0)
	{
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

二.扩展欧几里得算法

扩展欧几里得算法是基于欧几里得算法，求解形如 $ax+by=gcd(a,b)$ 的可行解的方法。

当 $gcd(a,b)=1$ 时，问题可转化为逆元的求解。

即：设 x 为 a 在模乘下的逆元，就有$ax\equiv1(mod\ b) \Rightarrow ax+bk=1$

该方法求解过程的核心在于

  • $gcd(a,b)=gcd=(b,a%b)=gcd(b,a-b\lfloor\frac{a}{b}\rfloor)$
  • $ax+by = bx’ + (a%b)y’$
  • $a%b=0$ 时，可取$x’=1,y’=0$使得等式成立

于是能得到递推式：

$ax+by=bx’ + (a-b\lfloor\frac{a}{b}\rfloor)y’$

进而：

  • $x=y’$
  • $y=x’-\lfloor\frac{a}{b}\rfloor y’$

那么便能将 $x’=1,y’=0$ 带入不断的回求 x 和 y。

1
2
3
4
5
6
7
8
9
10
11
12
void exgcd(int a, int b, int& x, int& y){
    if (!b) {
        x = 1;
        y = 0;

    } else {
        exgcd(b, a % b, x, y);
        int t = x;
        x = y;
        y = t - (a / b) * y;
    }
}