一， 扩展欧几里得
1 void exgcd(int a,int b,int &x,int &y) 2 { 3 if(b==0) 4 { 5 x=1;y=0;return; 6 } 7 exgcd(b,a%b,x,y); 8 swap(x,y); 9 y=y-a/b*x; 10 } 11 //a在%b意义下的逆元 12 //a*x+b*y=1的解->要求a与b互质才有解
二，费马小定理求逆元
要求：模数p为质数
费马小定理：a^(p-1)=1（mod p）
那么a^(p-2)=a^-1(mod p)
也就是说a的逆元为a^(p-2)
直接快速幂求逆元
三：快速求出多个数（1-n）的逆元
O(n)递推
1 inv[1]=1; 2 for(int i=2;i<=n;++i) 3 inv[i]=(ll)(p-p/i)*(ll)inv[p%i]%p; 4