逆元？
在取余的时候，+和×符合如下取余性质：
（a+b）%p=（（a%p）+（b%p））%p；
（a×b）%p=（（a%p）×（b%p））%p；对于减法，也有：（a-b+p）%p=（（a%p）-（b%p）+p）%p；（其中+p是为了避免负数运算）
但是除法布星。
所以我们引入了一个叫做逆元的东西。
逆元的定义
设b，使a×b≡1（mod p），称b为a在mod p意义下的逆元。
通常习惯使用inv[a]表示a的逆元。
这样：
（a/b）%p =（a/b）×1%p = （a/b）×（b×inv[b]）%p = （a×inv[b]）%p
于是， a / b ≡ a × inv[b] （mod p）
就可以取余了。
那么怎么求逆元呢？
用了这四种方法，他再也没有为求逆元的事操心过！
0.暴力枚举b值
1.费马小定理
根据费马小定理，在a，p互质，且p为质数的前提下，ap-1≡1（mod p）
那么有:
a × ap-2 ≡ 1 ( mod p )
所以ap-2就为a在mod p意义下的逆元。
用快速幂就行了，复杂度log.
优点：无脑 好打
缺点：有点慢，模数不为质数当场歇菜
1 int inv(int x) 2 { 3 int ans=1,k=p-2,base=x; 4 while(k) 5 { 6 if(k&1) 7 ans=(ans*base)%p; 8 base=(base*base)%p; 9 k>>=1; 10 } 11 return ans; 12 }
2.exgcd
exgcd能够在log的时间内求出ax+by=1的一组整数x,y解。
回到逆元的定义：
a*inv[a]≡ 1 (mod p) a*inv[a]=k*p+1 a*inv[a]+p*(-k)=1
得到exgcd的标准式，然后无脑套exgcd就好了，复杂度log.
优点：能解决p不为质数的恶心情况，通常比快速幂快
缺点：板子容易忘
1 int k,x,y; 2 void exgcd(int a,int b) 3 { 4 if(b==0) 5 { 6 x=1; 7 y=0; 8 return; 9 } 10 exgcd(b,a%b); 11 k=x; 12 x=y; 13 y=k-(a/b)*y; 14 return; 15 } 16 int inv(int c) 17 { 18 exgcd(c,p); 19 cout<<x<<endl;
20 }
3.线性递推
inv[i]=(p-p/i)*inv[p%i]%p
边界为inv[1]=1，一个for搞过去，贼爽。
不会证。就一句话，背住就行了。
复杂度O(n)，能够在线性时间内求出1~n的逆元。
优点：在某些问题上不可取代 简单优美
缺点：对求单个的逆元而言......
1 int inv[MAXN+1]; 2 int main() 3 { 4 inv[1]=1; 5 for(int i=2;i<=MAXN;++i) 6 inv[i]=(long long)(p-p/i)*inv[p%i]%p; 7 }
4.求阶乘的逆元
设b[i]为i的阶乘的逆元。（b[i] = inv[i!]）
首先暴力算出b[n]
然后从n-1到1循环：b[i]=(b[i+1]*(i+1))%p
妙不可言。
证明：
b[i]=inv[i]*b[i-1] b[i-1]=b[i]/inv[i]=b[i]*i b[i]=b[i+1]*(i+1)
复杂度O(n)，优缺点同上。
1 int inv[MAXN+1]; 2 int main() 3 { 4 int s=1; 5 for(int i=1;i<=n;++i) 6 s=(s*i)%p; 7 inv[n]=mypow(s,p-2);//要手写快速幂 8 for(int i=n-1;i>=1;--i) 9 inv[i]=(long long)inv[i+1]*(i+1)%p; 10 }
到底有个什么用呢？
求求组合数，
求求等比数列之和什么的
不会逆元现场歇菜。
还可以顺便让自己再背几遍超容易忘的exgcd（逃