求逆元(Inverse element)

*洛谷P3811 乘法逆元

1.费马小定理： \(x’ = x^{p-2}\)

2.线性递推求逆元：设 \(x’\) 表示 \(x\) 的逆元

对于 \(i\) ，求出 $t = p / i ，k = p % i $ 。

有 \(p = t \times i + k\) 。

所以 \(t \times i + k \equiv 0 ~(mod ~~p)\)

所以 \(t \times i \equiv -k ~(mod~~p)\)

左右同乘 \(i’k’\)

得 \(t \times k’ \equiv -i’ ~(mod~~p)\)

即 \(i’ \equiv -t \times k’ ~(mod~~p)\)

写成代码就是

inv[1] = 1;
for(int i = 2; i <= n; ++i)
	inv[i] = ((-(p / i) * inv[p % i]) % p + p) % p;
————————

*Rogue p3811 multiplicative inverse

1. Fermat’s small theorem: \ (x ‘= x ^ {P-2} \)

2. Linear recursive inverse element: let \ (x ‘\) represent the inverse element of \ (x \)

For \ (I \), find $t = P / I, k = P% I $.

Yes \ (P = t \ times I + K \).

So \ (t \ times I + K \ equiv 0 ~ (MOD ~ ~ p) \)

So \ (t \ times I \ equiv – K ~ (MOD ~ ~ p) \)

Multiply left and right \ (i’k ‘\)

Get \ (t \ times K ‘\ equiv – I’ ~ (MOD ~ ~ p) \)

That is \ (I ‘\ equiv – t \ times K’ ~ (MOD ~ ~ p) \)

Writing code is

inv[1] = 1;
for(int i = 2; i <= n; ++i)
	inv[i] = ((-(p / i) * inv[p % i]) % p + p) % p;