Mod 取模的用法

今天了大神的youtube https://www.youtube.com/watch?v=-OPohCQqi_E

加法

(a+b) % mod 这个是错的啊, 因为a+b已经overflow了, 所以要写成 ((a % mod) + (b % mod)) % mod

乘法

(a*b) % mod 这个也是错的啊, 因为a*b已经overflow了, 所以要写成 ((a % mod) * (b % mod)) % mod

减法

(a-b) % mod 这个是错的啊, 因为a-b不是如果是负的, 那么就是负数mod了, 但是a-b本身不存在overflow问题, 所以可以写成 ((a - b) % mod) + mod) % mod 这里的+ mod可以分两种情况考虑:

  • 如果(a-b)是正数, 那么+ mod 相当于没有.
  • 如果(a-b)是负数, 那么+ mod 相当于把负数变成正数后的mod.

除法

(a \ b) % mod 这个比较难, 按照大神说的, 要先用欧拉定理找到在1/b (mod), 然后做乘法. 那么怎么找到1/b (mod)? 需要用 pow(b, p-2) % p. 所以要写成 a * pow(b, p-2) % p

这里用的是 欧拉定理推导的https://en.wikipedia.org/wiki/Modular_multiplicative_inverse 模逆元

欧拉告诉我们 如果a和m互质, 那么

{\displaystyle a^{\phi (m)}\equiv 1{\pmod {m}},}

这个有个推式, 可以找到a的逆, 这个是费马小定理, 即是:

{\displaystyle a^{\phi (m)-1}\equiv a^{-1}{\pmod {m}}.}

这里的欧拉函数 phi(m) 是有多少个整数小于m且和m互质. 那么我们可以用这个定理推理出, 如果m本身就是一个质数, 那么和m互质的是m-1个数. 所以最上面那个p-2就是这么来的.

a^{{-1}}\equiv a^{{m-2}}{\pmod {m}}.