Congruence Equation

介绍

形如 ax \equiv c \pmod b 的方程被称为 线性同余方程(Congruence Equation)。

「NOIP2012」同余方程

求解方法

根据以下两个定理，我们可以求出同余方程 ax \equiv c \pmod b 的解。

定理 1：方程 ax+by=c 与方程 ax \equiv c \pmod b 是等价的，有整数解的充要条件为 \gcd(a,b) \mid c 。

根据定理 1，方程 ax+by=c ，我们可以先用扩展欧几里得算法求出一组 x_0,y_0 ，也就是 ax_0+by_0=\gcd(a,b) ，然后两边同时除以 \gcd(a,b) ，再乘 c 。然后就得到了方程 a\dfrac{c}{\gcd(a,b)}x_0+b\dfrac{c}{\gcd(a,b)}y_0=c ，然后我们就找到了方程的一个解。

定理 2：若 \gcd(a,b)=1 ，且 x_0 、 y_0 为方程 ax+by=c 的一组解，则该方程的任意解可表示为： x=x_0+bt ， y=y_0-at , 且对任意整数 t 都成立。

根据定理 2，可以求出方程的所有解。但在实际问题中，我们往往被要求求出一个最小整数解，也就是一个特解 x=(x \bmod t+t) \bmod t ，其中 t=\dfrac{b}{\gcd(a,b)} 。

代码实现 
int ex_gcd(int a, int b, int& x, int& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  int d = ex_gcd(b, a % b, x, y);
  int temp = x;
  x = y;
  y = temp - a / b * y;
  return d;
}
bool liEu(int a, int b, int c, int& x, int& y) {
  int d = ex_gcd(a, b, x, y);
  if (c % d != 0) return 0;
  int k = c / d;
  x *= k;
  y *= k;
  return 1;
}
buildLast update and/or translate time of this article，Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article OI-wiki
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

Comments