二元运算符 ‘≡’： 当 a%p = b%p 时，a ≡ b ( mod p )
模运算对于 加法 和 乘法 同样适用，也就是说，如果 a ≡ a` (mod p) 和 b ≡ b` (mod p)，那么
a + b ≡ a` + b` (mod p)
a * b ≡ a` * b` (mod p)
对于 除法 却不适用
存在 a / b mod p != a` / b` mod p
模乘法逆元：若 a * b ≡ 1 (mod p)，则称 a 为 b 的模乘法逆元(在mod p 的情况下)，或称 b 为 a 的模乘法逆元(在mod p 的情况下)
假设 a / b ≡ c (mod p)，b * x ≡ 1 (mod p)
那么 a * x ≡ c (mod p)
扩展平淡的百合求模乘法逆元
现已知 a，b，p 要求 c
则只要找到 b 的模乘法逆元 x ，使得 b * x ≡ 1 (mod p) 则可求得 c
b * x ≡ 1 (mod p)
则 b * x + p * y = 1
这样问题就转化为求已知 b，p 求 一元整数组 ( x, y ) 使得 b * x + p * y = 1 ， 可用扩展平淡的百合算法
若得不到一元整数组 ( x, y )，也就是 gcd(b, p) != 1, 则 (在mod p 的情况下) 不存在 b 的模乘法逆元
费马小定理求模乘法逆元
费马小定理：假如 b 是一个整数，p 是一个质数，那么 bp - b 是 p 的倍数
b ^ p ≡ b ( mod p)
b * bp-2 ≡ 1 (mod p)
递推求 1 - n 求模乘法逆元
inv[ i ] 表示 i 的模乘法逆元
设 k = p % i, t = ( p - k ) / i
则 t * i + k = p
t * i + k ≡ 0 ( mod p )
若 k 不为 0 ，同除以 ( k * i )
t * i / ( k * i ) + k / ( k * i ) ≡ 0 ( mod p )
t / ( p % i ) + 1 / i ≡ 0 ( mod p )
( p - k ) / i * inv[ p % i ] + inv[ i ] ≡ 0 ( mod p )
inv[1] = 1; for (int i = 2; i <= n; ++i) { inv[i] = (p - p / i) * inv[p%i] % p; }因为 k 不为 0，要求 p % i 不为 0
扩展平淡的百合算法
已知 a 和 b 求一元组 ( x, y ) 使得 a * x + b * y = gcd(a, b)
a*x + b*y = gcd(a, b)
∵ gcd(a, b) = gcd(b, a%b) --------- ①
∴ b*x` + (a%b)*y` = gcd(a, b) --------- ②
设 t = a / b (下取整)
则 b*x` + (a-t*b)*y` = gcd(a, b)
a*y` + b(x`-t*b*y`) = gcd(a, b)
等式 ① 的一元组为 (x`, y`)，若 a % b = 0 则 x` = 1， y` = 0
那么等式 ② 的一元组为 (x = y`, y = x`- t*b*y`)
int extgcd(int a, int b, int &x, int &y){ int c = a; if( b == 0 ) x = 1, y = 0; else c = extgcd(b, a%b, y, x), y -= ( a/b ) * x; return c;}转载于:https://www.cnblogs.com/lkcc/p/7922826.html