模运算(包含模的逆运算) | 您所在的位置:网站首页 › 大数取模java › 模运算(包含模的逆运算) |
模运算,就是取余数,在计算机语言中用%来表示。举个简单的例子,3 % 5 = 3。结果的取值范围在 0 与模之间,例如 res = X mod Y, 那么 res 的取值范围应该是[0,Y-1]。结果也可以用负数来看表示,3 % 5 = -2。 一般用正数的表现形式,如果出现负数,我们也该知道是怎么来的。 运算规律 模运算中同样有一些数学公式大家需要记住,基本跟四则运算比较相似。乘法大家需要注意下。 (A + B) % M = (A % M + B % M) % M (A - B) % M = (A % M - B % M) % M (A * B) % M = [(A % M) * (B % M)] % M (A^n) % M = [(A % M)^n] % M 同样,模运算也满足结合律,分配律,交换律: ((A + B) % M + C) % M == (A + (B + C)%M) %M ((A * B) % M * C) % M == (A * (B * C)%M) %M (A + B) % M == (B + A) % M (A * B) % M == (B * A) % M (A + B) % M == (A % M + B % M) % M [(A + B) % M * C] % M == [(A * C) % M + (B * C) % M] % M 模的逆元 在数学中,如果两个数a和b满足 a * b ≡ 1 (mod m),则我们称b是a在模m下的逆元。 通常表示为b = a^(-1) (mod m)。在模运算中,逆元一定存在于模数的范围内,因此逆元必须是正整数。如果逆元为负数,则与模运算的定义不符。因此,模的逆元一定是非负整数。 计算逆元最简单直观的方式就是辗转相除法,下面我将结合实例来讲解。 8^(-1) mod 29: ![]() ![]() 注意,此步骤替换的数均为每次计算的余数。如果最后出现的是负数,我们需要把它变成正数范围。 高阶次项取模: 比如 4^8 mod 59, 我们需要把次数一步步化小。 ![]() 这就是我目前所掌握到的模的运算,如有问题,感谢您的指正! |
CopyRight 2018-2019 实验室设备网 版权所有 |