class="markdown_views prism-atom-one-light"> 乘法逆元定义：当a*m=1 mod p时，则称m为a的乘法逆元，并由定义式可推得m*a+q*p=1，以此式子进行实际运算。
例1：求13模233的乘法逆元？
233=17*13+12
13=1*12+1
1=13-1*12=13-1*(233-17*13)=16*13+1*233
因此可得16即为13模233的乘法逆元。
乘法逆元存在的先决条件→两数互素
实现代码： inline long long extend_gcd(long long a,long long b,long long &x,long long &y) { if(a==0&&b==0) return -1ll; if(b==0) { x=1ll; y=0ll; return a; } long long d=extend_gcd(b,a%b,y,x); y-=a/b*x; return d; } inline long long mod_reverse(long long a,long long n) { long long x,y,d=extend_gcd(a,n,x,y); if(d==1) { if(x%n<=0)return x%n+n; else return x%n; } else return -1ll; }