Modular Inverse（模线性方程）

• lijunyu2005 发布于
• 1093 收藏

http://acm.sdut.edu.cn:8080/vjudge/contest/view.action?cid=89#problem/F 求解 ax≡1 (mod m). 原式相当于 ax(mod m) = 1(mod m),那么 ax-1 是m的倍数。 设ax-1 = my ——> ax - my = 1。 该式有解的前提是 1 是 a和m的最大公约数的倍数，因此 a 和 m 互质，方程...