数论-同余和逆元

同余（[x, y] 表示 lcm(x, y) ，(x, y) 表示 gcd(x, y) ）

常见法则：

若 a Ξ b (mod x) 且 a Ξ b (mod y) ，则 a Ξ b (mod [x, y]) 。

若 ka Ξ kb (mod x) ，则 a Ξ b (mod x/(x, k)) 。

逆元

线性求逆元的两种方法（假设是求模 MOD 意义下 i 的逆元）

1. 先求出 i! 的逆元 Jinv[i] 。用费马小定理求出 Jinv[N] 。由逆元定义 J[i+1] * Jinv[i+1] Ξ 1 ⇒ J[i] * (i+1) * Jinv[i+1] Ξ 1，故 Jinv[i] = (i+1) * Jinv[i+1] ，可以从 Jinv[N-1] 开始推得所有的 Jinv。由逆元定义 Jinv[i] * J[i] Ξ 1 ⇒ Jinv[i] * J[i-1] * i Ξ 1 。故 inv[i] = Jinv[i] * J[i-1] 。

1     J[0] = 1;
2     for (i = 1; i <= N; ++i) J[i] = J[i-1]*i%MOD;
3     Jinv[N] = Montgomery(J[N], MOD-2, MOD);
4     inv[N] = J[N-1]*Jinv[N]%MOD;
5     for (i = N-1; i >= 1; --i)
6         Jinv[i] = Jinv[i+1]*(i+1)%MOD;

2. 分解 MOD = k * i + b (b ∈ [0, i-1]) ，则 k = ⌊MOD / i⌋ ， b = MOD mod i 。

k * i + b Ξ 0 ⇒ k * i Ξ -b

两边同时乘 -inv[b] 得

i * k * -inv[b] Ξ 1

故 inv[i] = k * -inv[b] = -⌊MOD / i⌋ * inv[MOD mod i]。

1     inv[1] = 1;
2     for (i = 2; i <= N; ++i)
3         inv[i] = -MOD/i*inv[MOD%i]%MOD;

Update: 06 Aug, 2018 补充一个经典小 trick ，∑