乘法逆元
方法一:扩展欧几里得
lint ex_gcd(lint a,lint b,lint &x,lint &y)//扩展欧几里得(扩展gcd) { if (a==0&&b==0) return -1; if (b==0){x=1;y=0;return a;} lint d=ex_gcd(b,a%b,y,x); y-=a/b*x; return d; } lint mod_inverse(lint a,lint n)//乘法逆元 { lint x,y; lint d = ex_gcd(a,n,x,y); return (x%n+n)%n; }
方法二:费马小定理,快速幂
根据费马小定理:
已知p是质数且gcd(a, p) = 1,则 ap-1 ≡ 1 (mod p), 所以 a*ap-2 ≡ 1 (mod p)。
a^(p-2)就是a的逆元了
int find(int x) { int k=mod-2,ans=1; while(k) { if (k&1) ans=(lint)ans*x%mod; x=(lint)x*x%mod; k>>=1; } return ans; } x在%mod下的逆元
参考:逆元详解