结论
\(inv[i] = (mod − mod / i) \times inv[mod \% i] \% mod\)
证明
设 \(t = mod / i,k = mod \% i\)
则有：
\(t \times i + k \equiv 0 \quad \% mod\)
有：
\(−t∗i \equiv k \quad \% mod\)
两边同时除以 i∗ki∗k 得到：
\(−t∗inv[k] \equiv inv[i] \quad \% mod\)
即：
\(inv[i] \equiv −mod / i∗inv[mod \% i] \quad \%mod\)
即：
\(inv[i] \equiv (mod − mod / i)∗inv[mod \% i] \quad \% mod\)
证毕。
- 适用于模数 \(mod\) 是质数的情况，能够 \(O(N)\) 时间求出 \(1−N\) 对模 $ mod $ 的逆元。
代码
inv[1] = 1;
for(int i = 2;i<=1e7;i++)
inv[i] = 1ll*(mod-mod/i)*inv[mod%i]%mod;