取模运算

取模运算 mod %

取余和取模的区别

int c = a / b;
int m = a % b;

模运算规则

基本

1. (a + b) % p = (a % p + b % p) % p
2. (a - b) % p = (a % p - b % p) % p 
3. (a * b) % p = (a % p * b % p) % p 
4. (a ^ b) % p = ((a % p) ^ b) % p
    
1. ( 10 + 20 ) % 3 = ( 10 % 3 + 20 % 3 ) % 3 = 0

结合律

1. ((a + b) % p + c) % p = (a + (b + c) % p) % p
2. ((a * b) % p * c) % p = (a * (b * c) % p) % p

1. ((10+20) % 3 + 40) % 3 = (10+ (20+40) % 3 ) % 3 = 1

交换律

1. (a + b) % p = (b + a) % p
2. (a * b) % p = (b * a) % p

1. (10+20) % 3 = (20+10) % 3

分配律

1. (a+b) % p = ( a % p + b % p ) % p
2. ((a+b)% p * c) % p = ((a * c) % p + (b * c) % p) % p

1. (10+20) % 3 = (10 % 3 + 20 % 3) % 3
2. ((10+25) % 3 * 40) % 3 
    = (((10 % 3 + 25 % 3) % 3) * 40) % 3
    = ((10*40) % 3 +(25*40) % 3) % 3 
    = 2

重要定理

若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)
若a≡b (% p)，则对于任意的c，都有(a * c) ≡ (b * c) (%p)
若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)，
(a * c) ≡ (b * d) (%p)，(a / c) ≡ (b / d) (%p)