在算法中mod指的是什么意思-创新互联
小编给大家分享一下在算法中mod指的是什么意思，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！
在算法中，mod的意思是取模，就是取余数。mod运算，即求余运算，是在整数运算中求一个整数x除以另一个整数y的余数的运算，且不考虑运算的商。
mod运算，即求余运算，是在整数运算中求一个整数 x 除以另一个整数y的余数的运算，且不考虑运算的商。在计算机程序设计中都有MOD运算，其格式为：mod(nExp1,nExp2)，即是两个数值表达式作除法运算后的余数。
模p运算编辑
给定一个正整数p，任意一个整数n，一定存在等式
n = kp + r 其中k、r是整数，且 0 ≤ r < p，称呼k为n除以p的商，r为n除以p的余数。
对于正整数p和整数a,b，定义如下运算：
取模运算：a mod p 表示a除以p的余数。
模p加法：(a + b) mod p ，其结果是a+b算术和除以p的余数，也就是说，(a+b) = kp +r，则 (a+b) mod p = r。
模p减法：(a-b) mod p ，其结果是a-b算术差除以p的余数。
模p乘法：(a × b) mod p，其结果是 a × b算术乘法除以p的余数。
可以发现,模p运算和普通的四则运算有很多类似的规律，如：
结合律 | ((a+b) mod p + c)mod p = (a + (b+c) mod p) mod p ((a*b) mod p * c)mod p = (a * (b*c) mod p) mod p |
交换律 | (a + b) mod p = (b+a) mod p (a × b) mod p = (b × a) mod p |
分配律 | ((a +b)mod p × c) mod p = ((a × c) mod p + (b × c) mod p) mod p (a×b) mod c=(a mod c * b mod c) mod c (a+b) mod c=(a mod c+ b mod c) mod c (a-b) mod c=(a mod c- b mod c) mod c |
简单的证明其中第一个公式：
((a+b) mod p + c) mod p = (a + (b+c) mod p) mod p
假设
a = k1*p + r1
b = k2*p + r2
c = k3*p + r3
a+b = (k1 + k2) p + (r1 + r2)
如果(r1 + r2) >= p ，则
(a+b) mod p = (r1 + r2) -p
否则
(a+b) mod p = (r1 + r2)
再和c进行模p和运算，得到
结果为 r1 + r2 + r3 的算术和除以p的余数。
对右侧进行计算可以得到同样的结果，得证。
模p相等
如果两个数a、b满足a mod p = b mod p，则称他们模p相等，记做
a ≡ b (mod p)
可以证明，此时a、b满足 a = kp + b，其中k是某个整数。
对于模p相等和模p乘法来说，有一个和四则运算中迥然不同的规则。在四则运算中，如果c是一个非0整数，则
ac = bc 可以得出 a =b
但是在模p运算中，这种关系不存在，例如：
(3 x 3) mod 9 = 0
(6 x 3) mod 9 = 0
但是
3 mod 9 = 3
6 mod 9 =6
定理（消去律）：如果gcd(c,p) = 1 ，则 ac ≡ bc mod p 可以推出 a ≡ (b mod p)
证明：
因为ac ≡ bc (mod p)
所以ac = bc + kp，也就是c(a-b) = kp
因为c和p没有除1以外的公因子，因此上式要成立必须满足下面两个条件中的一个
1) c能整除k
2) a = b
如果2不成立，则c|kp
因为c和p没有公因子，因此显然c|k，所以k = ck'
因此c(a-b)=kp可以表示为c(a-b) =ck'p
因此a-b = k'p，得出a ≡ b (mod p)
如果a = b，则a ≡ b mod p 显然成立
得证
以上是“在算法中mod指的是什么意思”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注创新互联行业资讯频道！
当前文章：在算法中mod指的是什么意思-创新互联
网页URL：http://cdiso.cn/article/deisgc.html
