什么是逆元
所谓逆元是指对于一个二元运算$*$的集合而言,如果$e$是运算的单位远,那么$a*x=e$,就称$x$是$a$的逆元,比如对于加法而言,逆元就是0,对于乘法而言,逆元就是1。
现在这里讨论的是同余关系中的逆元,即$ax\equiv 1(mod m)$,对于给定的$a$,求解$x$。
如何求解
方程$ax\equiv 1(mod m)$其实等同与方程$ax-my=gcd(a,m)$,如此,便可以通过扩展欧几里得求解逆元,同时,这个方法指出有解的前提是$a$与$m$互质。
代码
|
|
Thanks ACM
所谓逆元是指对于一个二元运算$*$的集合而言,如果$e$是运算的单位远,那么$a*x=e$,就称$x$是$a$的逆元,比如对于加法而言,逆元就是0,对于乘法而言,逆元就是1。
现在这里讨论的是同余关系中的逆元,即$ax\equiv 1(mod m)$,对于给定的$a$,求解$x$。
方程$ax\equiv 1(mod m)$其实等同与方程$ax-my=gcd(a,m)$,如此,便可以通过扩展欧几里得求解逆元,同时,这个方法指出有解的前提是$a$与$m$互质。
|
|