逆元
费马小定理:如果p是质数(素数),并且gcd(a,p) == 1, 那么就会满足下面的式子
符号:≡是同余定理的一个专有符号。(意思:一定等于。)
在数论中,≡被用来描述一种等价关系,比如1≡5(mod 4)表示1除以4和5除以4的余数相同。
逆元解决的问题是当求(b/a)%mod时可能
设 a的逆元为inv,则inv=(a^(mod-2))%mod
证明如下:
则a*inv≡1(mod)并且 inv%mod=1/a%mod
原文地址:https://www.cnblogs.com/carcar/p/9498274.html