模數 modulus - 1

定義同餘關係

　　如果 a-b=kn 那麽說 a,b 是模n同餘的。n為正整數，k為整數。

加法 :

  (a + b) mod c = ((a mod c) + (b mod c)) mod c

減法 :

  (a - b) mod c = ((a mod c) - (b mod c)) mod c

乘法 :

  (a * b) mod c = ((a mod c) * (b mod c)) mod c

除法 : 

  定義倒數 (a^-1)

  a * (a^-1) mod b = 1

  用輾轉相除法獲得, gcd(a, b) = 1 , a 才有倒數. 

UVA - 10787

  (a + b) mod m = (a - b) mod m

=> (a + 2b) mod m = a mod m
=> 2b mod m = 0

所以任何 a 只要 2b mod m =0 就能做到


github

---

次方 : 連乘

費馬小定理 : 
    若模數是質數p，則次方的模數正是p-1。
     e.g. 2 (mod 7) ^ 100 ≡ 2 (mod 7) ^ 100 (mod 6)

    若模數是質數p，則倒數為 a 的 p-2 次方
     a * a ^ (p-2)  ≡ 1 (mod p)

---

UVA - 374 Big mod

a^2 mod m = a * a mod m = ((a mod m) * (a mod m) ) mod m

github Big mod