【数论】【逆元】【O(n)时间求出1~n对模MOD的逆元】 - 平头弟

【数论】【逆元】【O(n)时间求出1~n对模MOD的逆元】

2019-04-13 14:51发布生成海报

站内文章 / 模拟电子

15146 0

http://www.2cto.com/kf/201401/272375.html
新学的一个求逆元的方法： inv[i] = ( MOD - MOD / i ) * inv[MOD%i] % MOD 证明：设t = MOD / i , k = MOD % i 则有 t * i + k == 0 % MOD 有 -t * i == k % MOD 两边同时除以ik得到 -t * inv[k] == inv[i] % MOD 即 inv[i] == -MOD / i * inv[MOD%i] 即 inv[i] == ( MOD - MOD / i) * inv[MOD%i] 证毕适用于MOD是质数的情况，能够O(n)时间求出1~n对模MOD的逆

Ta的文章更多 >>

热门文章