利用费马小定理

如果p为质数，gcd(a,p)=1，那么a^(p-1) ≡1 (mod p) 
则a^(p-2) ≡1/a (mod p) 
a^(p-2) ≡ inv(a) (mod p) 
inv(a) = a^(p-2) (mod p) 
其中时间复杂度为O(logn) 注意：模数 mod必须为质数才可以利用费马小定理求解 typedef long long ll; ll quick_pow(ll a, ll b, ll yu) { ll ans = 1; a = a % yu; while (b) { if (b & 1) ans = ans * a%yu; a = a * a%yu; b >>= 1; } return ans; } ll inv(ll num) { return quick_pow(a,mod - 2,mod) }

利用扩展欧几里得

由公式a∗x+b∗y=gcd(a,b) 。 
若a，b互质且有解，则有a∗x+b∗y=1。 
当我们要求a关于b的逆元，我们可以这样看。 
a*x % b + b*y % b = 1 % b 
a*x % b = 1 % b 
a*x = 1 (mod b) 
可见，扩展欧几里德算法可以实现逆元。 typedef long long LL; void ex_gcd(LL a, LL b, LL &x, LL &y, LL &d)//扩展欧几里德 { if (!b) { d = a, x = 1, y = 0; } else { ex_gcd(b, a % b, y, x, d); y -= x * (a / b); } } LL inv(LL t, LL p)//如果不存在，返回-1 { LL d, x, y; ex_gcd(t, p, x, y, d); return d == 1 ? (x % p + p) % p : -1; }