求模运算怎么做?详细指南
1.取模运算是什么意思?
取模运算是求两个数相除的余数。
取模运算(“Modulo Operation”)和取余运算(“Remainder Operation ”)概念重叠但不完全一致。
主要的区别在于对负整数进行除法运算时操作不同。
取模主要是用于计算机术语中。
取余则更多是数学概念。
2.如何做取模运算?
如果 % 两边的操作数都为正数,则结果为正数或零;
如果 % 两边的操作数都是负数,则结果为负数或零。
C99 以前,并没有规定如果操作数中有一方为负数,模除的结果会是什么。
C99 规定,如果 % 左边的操作数是正数,则模除的结果为正数或零;
如果 % 左边的操作数是负数,则模除的结果为负数或零。例如:
15 % 2 // 余 1
15 % -2 // 余 1
-15 % 2 // 余 -1
-15 % -2 // 余 -1
标准规定,如果 a 和 b 都是整数,则 a % b 可以用公式 a - (a / b) * b 算出。例如:
-15 % 2 == -15 - (-15 / 2) * 2 == -15 - (-7) * 2 == -1
如果ax≡1(mod p),且a与p互质(gcd(a,p)=1),则称a关于模p的乘法逆元为x。(不互质则乘法逆元不存在)
求逆元的四种方法:
什么是逆元?
逆元--即逆元素,是指一个可以取消另一给定元素运算的元素
也就是说,你对A做了某种操作,得到A',现在你又用某个神奇的力量对A'操作,然后使A'又回到了A,这个神奇的力量就叫A的逆元(逆元素)
1.费马小定理
如果p是一个质数,而整数a不是p的倍数,则有a^(p-1)≡1(mod p)
引用一个大神的笔记:https://zhuanlan.zhihu.com/p/372089693?utm_source=wechat_session&utm_medium=social&utm_oi=775109650671476736
通过逆元的定义公式( )和费马定理的推论公式( )
得到(条件:a,p互素)
例如7d = 1 mod 40
这里出现了一个模幂运算,如何求模幂
2.欧拉定理求逆元 (相当于费马小定理的扩展)
3.扩展欧几里德
4.递推打表
一般使用费马小定理和和费马小定理的推广求逆元
3.取模运算代码实现
上一篇: MySQL中的取模运算操作详解
下一篇: 快速幂取模算法
推荐阅读
-
学习 C - 衍生(求模)运算的余数符号
-
求模逆运算
-
求模运算怎么做?详细指南
-
MySQL求模运算技巧解析
-
关于求模和求余-求余: 取整除后的余数。例如: 10 MOD 4=2; -17 MOD 4=-1; -3 MOD 4=-3; 4 MOD (-3)=1; -4 MOD 3=-1 如果有a MOD b是异号,那么得出的结果符号与a相同;当然了,a MOD b就相当于a-(a DIV B ) *b的运算。例如: 13 MOD 4=13-(13 DIV 4)*4=13-12=1 求模:
-
求模运算大揭秘:如何让 A 变回自己?答案就是找到它的逆元!
-
玩转科学计算器:模运算指南
-
探究Java中的除法运算和取模运算-B. 取模运算(求余数)