线性求逆元
时间复杂度:\(O(n)\)
问题：求取\(1...n\)关于质数\(p\)的逆元。
应用举例：求取组合数\(C_n^m \ mod \ p\),其中\(1 \leq n,m\leq10^7,p = 998244353\)。
\[C_n^m \equiv \frac {n!} {(n-m)!m!} (mod \ p)
\]
\[C_n^m\equiv n! * (n-m)!^{-1}*m!^{-1} (mod\ p)
\]
假设我们求取\(n\)关于质数\(p\)的逆元，即求取\(n^{-1}\)。
我们设\(a = \lfloor\frac{p}{n}\rfloor,b = p\ mod\ n\)。那么就有
\[a*n + b \equiv 0(mod\ p)\tag{1}
\]
对公式\((1)\)移项可得:
\[\begin{align*}
a*n &\equiv -b(mod\ p)\\
-\frac{a}{b} &\equiv n^{-1} (mod\ p)
\end{align*}
\]
即:
\[\begin{align*}
n^{-1} &\equiv -\frac{a}{b} (mod\ p)\\
&\equiv -\frac{\lfloor \frac{p}{n} \rfloor}{p\ mod\ n} (mod\ p)\\
&\equiv -\lfloor \frac{p}{n} \rfloor\cdot(p\ mod\ n)^{-1}(mod\ p)\\
&\equiv (p-\lfloor \frac{p}{n} \rfloor)\cdot(p\ mod\ n)^{-1}(mod\ p)\\
\end{align*}
\]
所以:
\[n^{-1} \equiv (p-\lfloor \frac{p}{n} \rfloor)\cdot(p\ mod\ n)^{-1}(mod\ p)
\]
无论\(p\)是多少，\(1\)的逆元就是\(1\).这是边界条件。
代码:
inv[1] = 1;
for(int i = 2;i<=n;i++)
{
inv[i] = (ll)(p - p/i)*(inv[p%i]) % p;
}