class="markdown_views prism-github-gist">

Solution

inv[i]=(mo−mo / i)∗inv[mo % i] % mo 证明： 设 t=mo / i ,k=mo % i ， 则有：t∗i+k≡0 (mod mo) 有： −t∗i≡k (mod mo) 两边同时除以 i∗k 得到： −t∗inv[k]≡inv[i] (mod mo) 即：inv[i]≡−mo / i∗inv[mo % i] (mod mo) 即：inv[i]≡(mo−mo / i)∗inv[mo % i] % mo 证毕。

• 适用于模数 mo 是质数的情况，能够 O(N) 时间求出 1−N 对模 mo 的逆元。

Code

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