取余公式

(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;
}