逆元相关
取余有很多好性质：
(a+b)%c=(a%c+b%c)%c(a∗b)%c=(a%c∗b%c)%c但是对于(a/b)%p，以上性质不能使用，只能用下面这条式子：
(a/b)%p=(a∗b−1)%p上式中b−1称为b在mod p意义下的逆元。
逆元有这样的性质：
b∗b−1≡1(mod p)逆元的求解方法主要有三种：
费马小定理加快速幂
费马小定理：
如果p是一个质数，而整数a不是p的倍数，则有ap−1≡1(mod p)。
注意只适用于p是质数且a不是p的倍数的情况：
b−1(mod p)≡bp−2(mod p)exgcd
void exgcd(int a,int b,int &x,int &y) {
if(!b) x=1,y=0;
else exgcd(b,a%b,y,x),y-=a/b*x;
int x,y;
exgcd(a,p,x,y);
x=(x%p+p)%p;
}
此时x是a在模p意义下的逆元，要求a与p互质，p可以不为质数。
为了证明上述过程的正确性，先介绍exgcd算法：
已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式：ax+by=gcd(a,b)。
贝祖定理：
定理描述如下：
a,b∈Z+exist x,y, ax+by=c⟺gcd(a,b)|c实际上观察：
a∗x≡1(mod p)可以化成：
a∗x−p∗y≡1(mod p)不妨把上式中的减号改成加号，得到：
a∗x+p∗y≡1(mod p)由于a与p互质，即gcd(a,b)=1，套用exgcd即可。
这里有两个有意思的结论：
- 如果x、y互质，那么不可用$xa+yb表示的最大正整数为x*y-x-y，其中a、b$都为自然数。
- 当 ai 和 xi 均为整数时, a1x1+a2x2+…+anxn的值一定为gcd(a1,a2,…,an)的整数倍。
在这道题中会用到。
线性递推
有时候可能需要预处理一大堆数据在模p意义下的逆元，这时候需要用到逆元的线性递推式。
inv[1]=1;
inv[i]=(p-p/i)*inv[p%i]%p;
简单证明如下：
首先：
1−1≡1(mod p)设：
p=k∗i+r即：
k=p/i,r=p%i则：
k∗i+r≡0(mod p)上式两边同时乘以：
i−1∗r−1得到：
k∗i∗i−1∗r−1+r∗i−1∗r−1≡0(mod p)注意到：
i∗i−1≡1(mod p)r∗r−1≡1(mod p)得到：
k∗r−1+i−1≡0(mod p)化简：
i−1≡−k∗r−1(mod p)即：
i−1≡−p/i∗(p%i)−1(mod p)为了防止负数取余，可以加上一个p：
i−1≡(p−p/i)∗(p%i)−1(mod p)证毕。
关于阶乘的逆元
做卢卡斯定理的时候可能会搞出很大数字的阶乘逆元，费马小定理显得太慢，可以线性递推出所有阶乘的逆元：
fac[0]=fac[1]=1;
for(int i=2;i<=MAXN;i++)
fac[i]=fac[i-1]*i%mod;
inv[MAXN]=qpow(fac[MAXN],mod-2);
for(int i=MAXN-1;i>=0;i--)
inv[i]=inv[i+1]*(i+1)%mod;
这样考虑：
inv[i+1]≡1(i+1)!(mod p)那么就有：
inv[i+1]∗(i+1)≡1i!(mod p)=inv[i]用费马小定理求出一个，其他的就可以用上式递推出来。
威尔逊定理
当且仅当p为素数时：
(p−1)!≡−1(mod p)素数的一个牛逼充要条件，但是不甚实用，阶乘会爆炸增长。
来做第一个留言的人吧！