取模运算详解
取模运算是求两个数相除的余数。取模运算(Modulo Operation)和取余运算(Remainder Operation)两个概念有重叠的部分但又不完全一致。主要的区别在于对负整数进行除法运算时操作不同。取模主要是用于计算机术语中。取余则更多是数学概念。给定一个正整数p,任意一个整数n,一定存在等式n = kp + r;其中 k、r 是整数,且 0 ≤ r < p,则称 k 为 n 除以 p
记录所学到的,也希望以后复习的时候可以在自己的blog看到。
什么是取模运算
概念——(来源于百度百科)
取模运算是求两个数相除的余数。
取模运算(Modulo Operation)和取余运算(Remainder Operation)两个概念有重叠的部分但又不完全一致。主要的区别在于对负整数进行除法运算时操作不同。取模主要是用于计算机术语中。取余则更多是数学概念。
定义——(来源于百度百科)
给定一个正整数p,任意一个整数n,一定存在等式 :
n = kp + r ;
其中 k、r 是整数,且 0 ≤ r < p,则称 k 为 n 除以 p 的商,r 为 n 除以 p 的余数。
取模运算的基本性质以及运算规则
基本性质
-
若p|(a-b),则a≡b (% p)。例如 11 ≡ 4 (% 7), 18 ≡ 4(% 7)
-
(a % p)=(b % p)意味a≡b (% p)
-
对称性:a≡b (% p)等价于b≡a (% p)
-
传递性:若a≡b (% p)且b≡c (% p) ,则a≡c (% p)
补充:
≡是同余符号,用于表示两个数模n同余的关系。如果a-b能被n整除,即(a-b)modn=0,那么就称整数a与b对模n同余,记作a≡b(modn)。
例如,3≡1(mod4)表示3和1对模4同余。
运算规则
模运算与基本四则运算有些相似,但是除法例外。其规则如下:
-
(a + b) % p = (a % p + b % p) % p (1)
-
(a - b) % p = (a % p - b % p ) % p (2)
-
(a * b) % p = (a % p * b % p) % p (3)
-
a ^ b % p = ((a % p)^b) % p (4)
-
结合律:((a+b) % p + c) % p = (a + (b+c) % p) % p (5)
((a*b) % p * c)% p = (a * (b*c) % p) % p (6)
-
交换律:(a + b) % p = (b+a) % p (7)
(a * b) % p = (b * a) % p (8)
-
分配律:(a+b) % p = ( a % p + b % p ) %p(9)
-
((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p (10)
重要定理
-
若a≡b (% p),则对于任意的c,都有(a + c)/ ≡ (b + c) (%p);
-
若a≡b (% p),则对于任意的c,都有(a * c) ≡ (b * c) (%p);
-
若a≡b (% p),c≡d (% p),则 (a + c) ≡ (b + d) (%p),(a - c) ≡ (b - d) (%p),(a * c) ≡ (b * d) (%p); (13)
主要资料都来源于百度搜索,同样取模运算运用在算法之中也比较常见;个人用的比较多的,也比较常见的是一些困难存在溢出的问题,例如:斐波那契数列的第n项与什么取模之类的。
希望上面的知识能够帮助到读者的你们,如果存在任何问题可以评论纠正
更多推荐
所有评论(0)