1. 乘法逆元 如果a·x≡1(mod p)且gcd(a,p)=1(即a,p互质)，那么x为模p意义下的乘法逆元。 一个数有逆元的充分必要条件是gcd(a,p)=1，此时逆元唯一存在。 2.拓展欧几里得求逆元 a·x≡1(mod p) 可以转化成a·x+p·y=1 求逆元即求x
typedef long long ll; ll exgcd(ll a, ll b, ll &x, ll &y) //扩展欧几里得算法 { if (b == 0) { x = 1, y = 0; return a; } ll t = exgcd(b, a % b, y, x);//注意是y,x y = y - a / b * x; return t; } ll Inv(int a, int mod) //求a在mod下的逆元，不存在逆元返回-1 { ll x, y; ll d = exgcd(a, mod, x, y); return d == 1 ? (x%mod+ mod) % mod : -1; //x可能是负数，转化成正数 }3.费马小定理/欧拉定理 模为素数时 费马小定理： 如果p是一个质数，而整数a不是p的倍数，则有a^p-1≡1(mod p)。 可以得到a*a^p-2≡1(mod p)。
很明显a^p-2就是a在模p意义下的逆元。 模不是素数时 欧拉定理: 若a、p为正整数且a、p互质，则有a^φ( p)≡1(mod p)。 可以得到a*a^(φ( p)-1)≡1(mod p)。
那么a^(φ( p)-1)就是a在模p意义下的逆元。
// 快速幂 ll qpow(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res % mod; } // 费马小定理 —— a在模p意义下的逆元 ll Inv(ll a, ll p) { return qpow(a, p - 2); }费马小定理时间复杂度：O (logmod)，mod为素数时常用，好写一些。 欧拉定理需要求欧拉函数值 φ ( p ) ，当p为素数时，欧拉定理就变成了费马小定理。
