逆元的意义：
通俗的讲，逆元可以看做一个数的倒数的整数形式，但是一个数的逆元在不同的 $ (mod) $ 意义下是不一样的。
$ a imes xequiv1 mod n quad $ ☞ $ quad a imes frac{1}{a}equiv1 mod n $
这个方程便是逆元的真正定义， $ x $ 的解即代表 $ a $ 在 $ mod n $ 意义下的逆元，通俗的讲：此时的 $ x $ 就相当于 $ a $ 的倒数，这样 $ a imes x $ 便会等于1，在 $ mod n $ 意义下余数必定为一。当然这个式子要建立在 $ a $ 与 $ n $ 互质的基础上！
可是逆元有什么用呢？直接用倒数不行吗？这是因为我们发现一个分数 $ mod $ 一个整数时是不能直接模运算的，但是可以进行乘法运算，我们就要用到逆元（一个数倒数的整数形式）
就像： $ frac{a}{b}mod (n) $ $ ot = $ $ frac{amod n}{bmod n}mod (n) $ 但是： $ frac{a}{b}mod (n) $ $ = $ $ a imes b^{-1}mod (n) $
所以当除运算碰上我们的模运算时，我们就需要 $ mod 模数 $ 意义下的逆元了！
单个逆元的求法：
1. 费马小定理：
对于整数 $ a $ 与质数 $ p $ ，若 $ a $ 与 $ p $ 互质，则有： $ a^{p-1}equiv1 mod p $
我们将上述定理稍稍变一下： $ a imes a^{p-2}equiv1 mod p $ （这不就是我们的逆元定义式吗？）
所以 $ a^{p-2} $ 就是 $ a $ 在 $ mod p $ 意义下的逆元啊！这个我们用快速幂求一下不就行了吗！
inline ll fast(ll x){//求x在%mod意义下的逆元
int y=mod-2;ll res=1;
while(y){
if(y&1)res=res*x%mod;
x=x*x%mod; y>>=1;
}return res;
}
2. 拓展欧几里得：
用快速幂求逆元，是敌不过某些毒瘤出题人，比如模数就是个long long，这样快速幂就会溢出。这个时候怎么办？嗯，我们的万能 $ gcd $ 就要登场了！（请不要理会博主的中二病，然后防爆longlong还可以用快速乘的）
- 存在整数 $ x_1 $ 和 $ y_1 $ ，使得： $ x_1 imes a+y_1 imes b=gcd(a,b) $
- 同理，存在整数 $ x_2 $ 和 $ y_2 $ ，使得： $ x_2 imes b+y_2 imes (amod b) =gcd(b,amod b) $
根据我们万能 $ gcd $ 的性质，上述两个等式的右半部分相同，同理它们的左半部分也相同！
于是我们得到：
- $ x_1 imes a+y_1 imes b=x_2 imes b+y_2 imes (amod b) $
- $ x_1 imes a+y_1 imes b=x_2 imes b+y_2 imes (a-frac{a}{b} imes b) $
- $ x_1 imes a+y_1 imes b=y_2 imes a+(x_2-y_2 imes frac{a}{b}) imes b $
- $ x_1=y_2 quad $ $ quad y_1=x_2-y_2 imes frac{a}{b} $
所以我们根据 $ x_2 $ 和 $ y_2 $ 就能求出 $ x_1 $ 和 $ y_1 $ 辣！而众所周知的，我们 $ gcd $ 大法的终极形态就是当 $ b0 $ 的时候，这时我们的 $ x=1 $ ，而因为 $ b0 $ ，所以我们的 $ y $ 随便取一个就行（好像都用0的），然后我们在回溯的时候，不断往前推我们的 $ x $ 和 $ y $ ，直到得出我们最初的哪一组解。（这其实就是一个构造的过程）
可是这和求逆元又有什么联系呢？我们发现只有当我们的 $ a $ 与 $ b $ 互质的时候即 $ gcd(a,b)=1 $ 时，这个二元一次方程不就变成了： $ x_1 imes a+y_1 imes b=1 $ （等同于 $ x_1 imes a=1(mod b) $ 或 $ y_1 imes b=1(mod a) $ ）而这，不就相当于我们逆元的定义式吗？我们再用上述方法将 $ x_1 $ 和 $ y_1 $ 求出来，不就是逆元了吗？
inline int exgcd(int a,int b,int &x,int &y){
if(b==0)return x=1,y=0,a;
int d=exgcd(b,a%b,y,x);
y-=(a/b)*x; return d;
}
递推求多个逆元：
上面我们说的是单个求逆元的方法，复杂度为 $ O(logn) $ 级别（一般快速幂要快一些），可是有一些题目往往需要我们求多个逆元（如连续的数，阶乘，和次方的逆元），而且单个求的时间往往要在 $ O(1) $ 的复杂度，我们有没有办法 $ O(n) $ 求出所有这些逆元呢？答案是可以的，但只能是一些特殊的数。
线性求逆元：
同余是神奇的，我们可以通过它推出一个逆元的递推式：
$ Rightarrow inv[i]=(m-m/i) imes inv[m mod i] mod m $
推导过程：设 $ a=m/i $ ，设 $ b=m mod i $ ，则有 $ m=a imes i+b $
$ Rightarrow a imes i+bequiv 0mod(m) $
$ Rightarrow -a imes iequiv bmod(m) $
我们将同余号两边都除以一个 $ i imes b $ ，把逆元这个概念引进来，得到：
$ Rightarrow -a imes inv[b]equiv inv[i]mod(m) $
这样，我们就将 $ i $ 和 $ m mod i $ 联系到了一起，我们将 $ a $ 和 $ b $ 换回原装可得：
$ Rightarrow -m/i imes inv[m mod i]equiv inv[i]mod(m) $
$ Rightarrow inv[i]equiv (m-m/i) imes inv[m mod i] mod(m) $
$ Rightarrow inv[i]=(m-m/i) imes inv[m mod i] mod m $
这样，只要我们预处理一下 $ inv[1]=1 $ ，往后的所有逆元我们都能线性求了！
int main(){
n=qr(),m=qr(); inv[1]=1;
for(int i=2;i<=n;i++)
inv[i]=(ll)(m-m/i)*inv[m%i]%m;
return 0;
}
线性求阶乘逆元： （这个比上面的要简单一些。）
我们都知道，阶乘代表： $ n!=1 imes 2 imes 3... imes n $ ，那么我们可以得出： $ (n-1)!=n!/n $
这不也是一个逆元式吗？只不过我们要倒着递推而已。
我们先用快速幂或拓展欧几里得求出 $ n! $ 的逆元，然后所有比它小的逆元都可以线性推过去了！
int main(){
n=qr(),m=qr(); jc_inv[n]=1;
for(int i=n;i>=2;--i)
jc_inv[i-1]=(ll)jc_inv[i]*i%m;
return 0;
}