求逆元

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 using namespace std;
 5 typedef long long LL;
 6 // 求x和y使得ax+by=d并且|x|+|y|最小。其中d=gcd(a,b)
 7 void exgcd(LL a,LL b,LL& d,LL& x,LL& y){
 8     if(!b) d = a,x = 1,y = 0;
 9     else{
10         exgcd(b,a % b,d,y,x);
11         y -= x * (a / b);
12     }
13 }
14 // 计算模n下a的逆，如果gcd(a,n) != 1，则逆不存在，返回-1
15 LL inv(LL a,LL n){
16     LL d,x,y;
17     exgcd(a,n,d,x,y);
18     return d == 1 ? (x + n) % n : -1;
19 }
20 int main(){
21     printf("%lld
",inv(7,15));
22 }

也可以由欧拉定理，对任意a属于Zn，a^(phi(n))=1(modn)。于是a的逆就是a^(phi(n) - 1)。

如果n是素数的话，a的逆就是pow_mod(a,n-2,n)

1 //如果n是素数
2 LL inv(LL a,LL n){
3   return pow_mod(a,n - 2,n);
4 }