引言.
在做算法题的过程中，经常需要取模操作，对结果模上1e9+7或者1e9+9或者998244353。但有时会发现题目A不了最后是取模的问题，为了在日后的题目完成过程中避免因取模而出错，因此整理一下取模相关的知识。
文章目录
1. 取模运算和取余运算：
这一部分的内容介绍取模和取余的区别，是作为基础补充，到后续部分会用到，可先跳过该节，到时候反过来看
对于整数a和b， a % b a\%b a%b 的运算方式如下（取余和取模一样）：
- 求整数商： c = [ a / b ] c=[a/b] c=[a/b]
- 计算模或者余数： r = a − c × b r=a-c\times b r=a−c×b
在整数商中有一个取整操作，取模和取余的不同在于：
| 运算 | 取整方式 |
|---|---|
| 取模 | 求整数商时, 取整向负无穷靠近, 即: − 1 / 3 → − 1 -1/3 \rightarrow -1 −1/3→−1 |
| 取余 | 求整数商时, 取整向0靠近, 即: − 1 / 3 → 0 -1/3 \rightarrow 0 −1/3→0 |
很容易发现, 当 a / b a/b a/b为正数时, 取余和取模的结果是一样的, 只有当其为负数时, 两者才存在区别. 为了方便理解, 下面给出一个例子: 求 − 10 % 3 -10\%3 −10%3 的模和余数.
| 运算 | 整数商 | 结果 |
|---|---|---|
| 取模 | -4 | 2 |
| 取余 | -3 | -1 |
接下来要记住一个结论:
- C/C++, Java 的
%为**取余** - Python的
%为**取模**
可以看到, 取余运算在a或者b为负数时得到的余数仍为负数, 而取模则能得到正数, 这一点在后续的做题过程中会意识到.
2. 为什么总是对这几个数取模?
按照规律一条条陈述, 结论不言而喻
- 整数类型(int, 64位操作系统上, 占4个字节)的范围是: − 2 31 ∼ 2 31 − 1 -2^{31}\sim2^{31}-1 −231∼231−1
-
1e9+7,1e9+9,998244353这三个数都小于 2 30 2^{30} 230, 因而对于任意两个模过之后的数 a a a和 b b b:- a,b < 2 30 \text{a,b} \lt 2^{30} a,b<230
- a + b < 2 31 a+b \lt 2^{31} a+b<231
- a b < 2 60 ab \lt 2^{60} ab<260, 在long long范围内不会溢出
- 可以使用
扩展欧几里德算法
3. 扩展欧几里德算法1:
3.1 欧几里德算法(也叫辗转相除法):
gcd(a, b) = gcd(b, a mod b)
3.2 扩展欧几里德算法:
贝祖定理(也叫裴蜀定理)： 给定两个整数a, b, 必定存在整数x、y使得 a x + b y = g c d ( a , b ) ax+by=gcd(a,b) ax+by=gcd(a,b) ⇒ \Rightarrow ⇒ 如果ax+by=1有解，那么gcd(a,b)=1；
扩展欧几里德算法可以用来求模反元素（模逆元）的。
3.2.1 符号约定:
| 符号 | 含义 |
|---|---|
| g c d ( ⋅ ) gcd(\cdot) gcd(⋅) | 欧几里德算法 |
| [ ⋅ ] [\cdot] [⋅] | 向0取整 |
3.2.2 算法思想:
a x + b y = g c d ( a , b ) = g c d ( b , a % b ) = g c d ( b , a − [ a b ] b ) 取 某 一 x ′ , y ′ 得 : a x + b y = b x ′ + ( a − [ a b ] b ) y ′ = g c d ( a , b ) 故 而 : a ( x − y ′ ) + b ( y − x ′ + [ a b ] y ′ ) = 0 恒 成 立 ⇒ { x = y ′ y = x ′ − [ a b ] y ′ ax+by=gcd(a, b) =gcd(b, a\%b)=gcd(b, a-[\frac{a}{b}]b) \\ 取某一x', y'得:ax+by=bx'+(a-[\frac{a}{b}]b)y'=gcd(a,b) \\ 故而:a(x-y')+b(y-x'+[\frac{a}{b}]y')=0恒成立 \\ \Rightarrow \begin{cases} x = y' \\ y = x' - [\frac{a}{b}]y' \end{cases} ax+by=gcd(a,b)=gcd(b,a%b)=gcd(b,a−[ba]b)取某一x′,y′得:ax+by=bx′+(a−[ba]b)y′=gcd(a,b)故而:a(x−y′)+b(y−x′+[ba]y′)=0恒成立⇒{x=y′y=x′−[ba]y′
类似于gcd(
⋅
\cdot
⋅), x’和y’的求法也是递归进行的, gcd(
⋅
\cdot
⋅)的终结条件是: b = 0, 此时:
{
x
=
y
′
=
1
y
=
0
\begin{cases} x = y' = 1 \\ y = 0 \end{cases}
{x=y′=1y=0
得到递归基后, 可以将递归基作为新的x’, y’, 来求上一步的x, y
3.2.3 求模逆元:
对于 a b % n = 1 ab\%n=1 ab%n=1, b称为a的模逆元(反之亦然)
3.2.3.1 费马小定理:
假设p为质数, 那么 a ( p − 1 ) % p = 1 a^{(p-1)} \% p=1 a(p−1)%p=1.
推论: a p − 2 a^{p-2} ap−2为a%p的乘法逆元 ( a × a p − 2 % p = a p − 1 % p = 1 a\times a^{p-2} \% p = a^{p-1} \% p = 1 a×ap−2%p=ap−1%p=1)
3.2.3.2 扩展欧几里德算法: [待完善, 还没完全理清]
a b % p = 1 ⇒ a b % p + k p % p = 1 (kp%p必然为0, 因此最外层不需要加%) 若 g c d ( a , p ) = 1 , 则 : a x + p y = 1 ab\%p = 1 \Rightarrow ab \%p + kp\%p = 1 \text{ (kp\%p必然为0, 因此最外层不需要加\%)} \\ 若gcd(a, p) = 1, 则: ax + py = 1 \\ ab%p=1⇒ab%p+kp%p=1 (kp%p必然为0, 因此最外层不需要加%)若gcd(a,p)=1,则:ax+py=1
参考资料:
-
https://zhuanlan.zhihu.com/p/58241990 ↩︎