MENU

求解同余方程

February 25, 2019 • Read: 3774 • 算法阅读设置

前置知识

$a,b$ 对 $m$ 取模的结果相同,记为 $a\equiv b (mod\ m)$,即 $a\ mod\ m == b\ mod\ m$

如果 $a\equiv b (mod\ m)$,且 $c\equiv d (mod\ m)$,则

  • $a + b\equiv c + d(mod\ m)$
  • $a \times b\equiv c \times d(mod\ m)$

同余方程

设有同余方程 $ax\equiv b (mod\ n)$ 对于未知数 $x$ 有解,当且仅当 $b$ 是 $gcd (a,n)$ 的倍数。且方程有解时,方程有 $gcd (a,n)$ 个解

求解方程 $ax\equiv b (mod\ n)$ 相当于求解方程 $ax+ny=b$($x,y$ 为整数)

对于上面的式子证明如下:

由 $ax \equiv b (mod\ n)$ 得

$$ ax = ny_1 + p\\ b = ny_2 + p $$

用中文解释就是,$ax$ 等于 $y_1$ 倍的 $n$ 加上余数 $p$;而 $b$ 等于 $y_2$ 倍的 $n$ 加上余数 $p$

两式相减得 $ax+ny=b$,证毕

所以求解同余方程 $ax\equiv b (mod\ n)$ 就转化为了求解裴蜀方程 $ax+ny=b$,并且 $(x,y)$ 有整数解当且仅当 $b$ 为 $gcd (a,n)$ 的倍数

例题 POJ1061 青蛙的约会

Archives Tip
QR Code for this page
Tipping QR Code