模运算
作者:
码上成功
,
2024-02-16 14:49:19
,
所有人可见
,
阅读 95
模运算(重点乘法)
在C++中,一个数太大,无法直接输出,或者不需要直接输出,那么可以对它取模,缩小数值再输出。
模运算:a除以m的余数
a mod m=a % m
0<= a mod m <=m-1
例如m=10,就是取a的个位数
例如m=2.若余数为0,表示a为偶数,否则a为奇数。
//
**模运算的性质**(注意,在减法中,可能会出现负数情况,在计算机中对负数取模是比较难搞的,但是减法在题目中较少出现)
_加_:(a+b) mod m = ((a mod m) + (b mod m)) mod m
_减_:(a - b) mod m = ((a mod m) - (b mod m)) mod m
_乘_:(a*b) mod m= ((a mod m)*(b mod m)) mod m
但是,除法这样做是错的:
(a/ b) mod m = ((a mod m) / (b mod m)) mod m
例:
(100/50) mod 20=2
(100 mod 20) / (50 mod 20) mod 20 = 0
两者不相等。
除法的取模,需要用到逆元