在算法竞赛中经常会用到各式各样的取模运算, 下面将常用的总结下来以便自己复习
什么是取模运算
在 java 和 c/c++ 中
对于整型数 a,b 来说, 取模运算:
1. 求整数商: c = a/b;
2. 计算模: a % b = a - c * b;
例子:
- 9 % 4 = 9 - (9 / 4) * 4 = 1
- 9 %-4 = 9 - (9 /-4) -4 = 1
- -9 % 4 = -9 - (-9 / 4) 4 =-1
- -9 %-4 = -9 - (-9 /-4) *-4 =-1
在 python 中
a % b = a - n b, 其中 n 为不超过 a / b 的最大整数
1. 求商: c = a / b
2. 取 n:n 为不超过 c 的最大整数即 [c]
3. 计算模: a % b = a - nb
取模运算的性质
模运算与基本四则运算有些相似, 但是除法例外. 其规则如下:
- (a + b) % p = (a % p + b % p) % p
- (a - b) % p = (a % p - b % p) % p
- (a * b) % p = (a % p * b % p) % p
- a ^ b % p = ((a % p)^b) % p
结合律:
- ((a+b) % p + c) % p = (a + (b+c) % p) % p
- ((ab) % p c)% p = (a * (bc) % p) % p
交换律:
- (a + b) % p = (b+a) % p
- (a b) % p = (b * a) % p
分配律:
- (a+b) % p = ( a % p + b % p ) % p
- ((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p
- tips
当我们只关注某个整数的后 k 位时我们可以利用取模运算
例如:
long long x = 12345678911;
我们只关注这个数的后 4 位可以利用 temp = x % 10^4
利用这个 temp 代替 x 与其他数字的四则运算
来源: http://www.bubuko.com/infodetail-3256018.html