【算法】数论---取模运算法则

取模运算(余数运算)有一些基本的运算法则:

  • (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 ^ b % p = ((a % p)^b) % p

取模运算(余数运算)有一些基本的性质:

同余性质: 如果两个整数 a 和 b 对于某个正整数 m 有 a % m = b % m,那么 a 和 b 被称为对模 m 同余,记作 a ≡ b (mod m)。