ll exgcd(ll a, ll b, ll &x, ll &y)// 拓欧 { if (b == 0) { x = 1; y = 0; return a; } ll d = exgcd(b, a % b, y, x); y -= (a / b) * x; return d; } ll inv(ll a, ll p) { ll x, y; if (exgcd(a, p, x, y) != 1) // 无解的情形 return-1; return (x % p + p) % p; }
费马小定理
费马小定理叙述如下:
若是质数,且,则有
从逆元的定义可以推导:,于是有。
于是对算一下快速幂即可。注意:这个方法的前提是:是质数。
inline ll qpow(ll a, ll n, ll p)// 快速幂 { ll ans = 1; while (n) { if (n & 1) ans = ans % p * a % p; a = a % p * a % p; n >>= 1; } return ans; } inline ll inv(ll a, ll p) { returnqpow(a, p - 2, p); }