2016.7.22[UPD]修改若干BUG。补充逆元存在充分性证明，时间复杂未知的算法，附上欧拉定理的证明。
概述
本文对逆元进行探究，从群论角度给出定义并提供例子，探讨了一些逆元的性质，并给出若干种计算逆元的算法。
<!--
Abstrct
This article explores the backgound of the inverse element, give definition to the inverse with the Group Theorem, explores some properties of the inverse, and give out some algorithms on calculating inverse elements.-->
若干定义
群：对于一个集合$ S $，在其上定义一个二元运算$ \times $，记为群$ G(S,\times ) $。
幺元：在群$ G(S,\times) $中，幺元是指存在一组元素满足如此性质：设$ i \in S $，对任意$ a \in S $ 有$ i \times a = a $。
逆元：在群$ G(S,\times) $中的幺元$ E $，对元素$ a \in S $，有对应元素$ a^{-1} \in S $使得$ a \times a^{-1} = E $，则$ a^{-1} $称为$ a $的逆元。若$ \times $满足交换律，则$ a $与$ a^{-1} $互为逆元，且$ G $被称为交换群。有可能有元素不存在逆元。
逆元我们其实见得很多，比方说
加法：在群$ G(\mathbb R,+) $中，幺元为$ 0 $，任意一个数均有逆元，任意一组相反数互为逆元。
乘法：在群$ G(\mathbb R \setminus \\{0\\} ,\times) $中，幺元为$ 1 $，任意一个数均有逆元，任意一组倒数互为逆元。
矩阵乘法：在群$ G(M, \cdot) $，$ M $为矩阵集，$ \cdot $为矩阵乘法，幺元是单位矩阵集
$$
\left\\{
\begin{bmatrix}
1 \& 0 \& \cdots \& 0 \\\\
0 \& 1 \& \cdots \& 0 \\\\
\vdots \& \vdots \& \ddots \& \vdots \\\\
0 \& 0 \& \cdots \& 1
\end{bmatrix}
\right\\}
$$
可能有一些矩阵不存在逆元。这些矩阵被称为奇异的。
在OI中，逆元一般是用来对付带模乘法的。
即是对于群$ G( \mathbb Z_+ , \times) $的任意$ a \in \mathbb Z_+ $都有唯一的$ x \in \mathbb Z_+ $满足 $$ ax \equiv 1 \pmod p \tag{\*}\label{\*}$$其中$ a, x $互为逆元，$ p $一般为质数。
更一般情况：
定理1 逆元存在当且仅当$ a,p $互质，即$$ gcd(a,p)=1 \tag{\*\*}\label{\*\*} $$
证明 首先证必要性。用反证法。不妨设逆元$ x $存在，则满足关系$ adx \equiv 1 \pmod {cd} $，其中$ d \neq 1 $，变型得$$ abd-cdy=1 \\\\ (ab-cy)d=1 $$
而$ d,(ab-cy) \in Z_+ $，则必有$ d = ab - cy = 1 $，与题设矛盾。
证充分性。模$ P $下$ \\{ 0,1,\cdots,P-1 \\} $构成完全剩余系，则由完全剩余系性质，当$ (a,p)=1 $时$ \\{ 0, a, \cdots, a(P-1) \\} $也为完全剩余系，而后者之中必存在$ 1 $，故$ a $必存在逆元。同理可证欧拉定理，见附A。
感谢@whj同学提供充分性证明思路。证毕
如何求单个逆元
1 拓展欧几里得算法
知识需求：欧几里得算法
我们来将$\eqref{\*}$变一下形。
$$
\eqref{\*} \Rightarrow ax = 1 - py
\Rightarrow ax + py = 1 \stackrel{\eqref{\*\*}}= gcd(a,p)
$$
我们已经知道了$ a,p $的值，那么求$ a $的逆元$ x $，就可以直接通过拓展欧几里得算法得到$ x $了。
注意这个$ x $有可能为负数，所以我们一般得出解后要加上一个模数$ p $。
复杂度是$ O(\lg n) $。
Algorithm 1.1
exgcd(a, p, inv, no_use_1, no_use_2);
inv = (inv + p) % p;
2 快速幂
知识需求：快速幂
我们需要引入一个引理(Fermat, 1636)：当$ p $为质数，且$ (a,p)=1 $时$$ a^{p-1} \equiv 1 \pmod p $$
容易看出，$ a $逆元为$ a^{p-2} $。
那么只需一个快速幂即可完成，但只限于$ p $为质数的情况。
复杂度是$ O(\lg n) $
Algorithm 1.2
inv = power(a, p - 2, p);
3 小结
以上两种方法各有优缺点，并不是所有逆元两种方法都能出正解，选用时要考虑题目实际和编程复杂度使用。
如何预处理逆元
单个求逆元的复杂度是$ O(\lg n) $。若我们需要求$ n $内所有数模奇质数$ P $的逆元，一个一个求需要$ O(n \lg n) $，远远达不到理论下界的$ O(n) $。下面我们就来研究一下理论下界。
1 求$ P $以内逆元
设$ t = \lfloor \frac{P}{i} \rfloor, k = P \\, \mathbf{mod} \\, i $，则有$ t \cdot i + k = P $，即
$$ t cdot i+k equiv 0 pmod P \\
-t cdot i equiv k pmod P \\$$
两边除以$ i \cdot k $
$$ -t cdot k^{-1} equiv i^{-1} pmod P \\
(P-lfloor frac{P}{i} rfloor) cdot (P \, mathbf{mod} \, i)^{-1} equiv i^{-1} pmod P \\
i^{-1}=((P-lfloor frac{P}{i} rfloor) cdot (P \, mathbf{mod} \,i)^{-1}) \, mathbf{mod} \, P $$
将$ i^{-1} $记为$ inv[i] $，即
$$ inv[i]=((P-\lfloor \frac{P}{i} \rfloor) \cdot inv[P \\, \mathbf{mod} \\,i]) \\, \mathbf{mod} \\, P \tag{\*\*\*}\label{\*\*\*}$$
这样就得出了递推公式，初始化$ inv[1]=1 $就能在线性时间求出所有所有数的逆元。但需注意，$ P $需为质数，否则会有一些特定的$ i $递归后使得$ P \\, \mathbf{mod} \\, i = 0$，而0没有逆元。当然若保证不会存在此$ i $，则可忽略上述限定。
Algorithm 2.1
int inv[mod] = {0};
void getinv()
{
inv[1] = 1;
for(int i = 2; i < mod; i++)
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
2 筛法求逆元
注意到逆元是可乘的，即$ (ab)^{-1}=a^{-1} \cdot b^{-1} $。换言之，令函数$ f(i) $表示$ i $的逆元，则$ f $是完全积性函数。和线性筛质数一样，只要预处理$ P $以内各个质数的逆元，全部数的逆元也都能求出。求单个质数的逆元是$ O(\lg P) $，而P以内质数有$ O\left(\frac{P}{\lg P}\right) $个，所以复杂度仍是线性的$ O(P) $。
3 阶乘的逆元
话说在Codeforces #313 div.2 E/div.1 C的组合数取模中，看A的人的预处理逆元的代码就感觉不知所云。自己无奈打了个暴力幸好没卡。今天（2015.8.3）回想了一下发现其实很好证。
$$ [(i+1)!]^{-1} \\
=[(i+1) cdot i!]^{-1} \\
=(i+1)^{-1} cdot (i!)^{-1}$$
变形得$$ (i!)^{-1}=(i+1) \cdot [(i+1)!]^{-1} $$
Algorithm 2.2
int fac[maxn], inv[maxn];
void getinv(int n)
{
fac[0] = 1;
for(int i = 1; i < n; i++)
fac[i] = fac[i - 1] * i % mod;
inv[n - 1] = power(fac[n - 1], mod - 2);
for(int i = n - 2; i > 0; i--)
inv[i] = inv[i + 1] * (i + 1) % mod;
}
一个时间复杂度玄学的求单个逆元法
在第二个参考链接中曾经给出一种求单个逆元的所谓$ O(\lg n) $方法，其思想即为2-1中提出的方法，只是将递推换成了递归。
function inv(i)
return (mod - mod / i) * inv(mod % i) % mod;
其理由为$ mod \\% i $每次会将$ i $规模减半。实际上当$ mod=n!-1 $，$ n $为所需求逆元的数，此时$ mod \\% n = n - 1 $并不会减半，这时为$ O(n!^{-1}) $（反阶乘）。只是其他情况复杂度很难做出分析，不知有谁能指教。
@wyh：实践中跑得很快就可以啦！
参考
ACdreamer
miskcoo
附
A 欧拉定理
定理A 对于$ a,p \in \mathbb Z_+ $且$ (a,p)=1 $，有$$ a^{\varphi(n)} \equiv 1 \pmod p $$
证明 模$ p $下与p互质的数$ \\{ a_1,\cdots,a_{\varphi(p)} \\} $构成wyh剩余系，相似于完全剩余系，则由完全剩余系性质，当$ (a,p)=1 $时$ \\{ aa_1, \cdots, aa_{\varphi(p)} \\} $也为完全剩余系。此时$ a^{\varphi(p)} \prod_{1}^{\varphi(p)} a_i \equiv \prod^{\varphi(p)}_{1} a_i \pmod p $，即$$ a^{\varphi(p)} \equiv 1 \pmod p $$证毕