首页 > 代码库 > O(n)求1~n的逆元

O(n)求1~n的逆元

 

原地址:http://www.2cto.com/kf/201401/272375.html

 

前提是MOD是个素数。 

新学的一个求逆元的方法:

inv[i] = ( MOD - MOD / i ) * inv[MOD%i] % MOD

证明:

设t = MOD / i , k = MOD % i

则有 t * i + k == 0 % MOD  //(t*i+k) = 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]

证毕

能够O(n)时间求出1~n对模MOD的逆

O(n)求1~n的逆元