线性同余方程

介绍

形如 的方程被称为 线性同余方程(Congruence Equation)。

「NOIP2012」同余方程

求解方法

根据以下两个定理，我们可以求出同余方程 的解。

定理 1：方程 与方程 是等价的，有整数解的充要条件为 。

根据定理 1，方程 ，我们可以先用扩展欧几里得算法求出一组 ，也就是 ，然后两边同时除以 ，再乘 。然后就得到了方程 ，然后我们就找到了方程的一个解。

定理 2：若 ，且 、 为方程 的一组解，则该方程的任意解可表示为：，, 且对任意整数 都成立。

根据定理 2，可以求出方程的所有解。但在实际问题中，我们往往被要求求出一个最小整数解，也就是一个特解 ，其中 。

代码实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
// C++ Version
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
# Python Version
def ex_gcd(a, b ,x, y):
  if b == 0:
      x = 1; y = 0
      return a
  d = ex_gcd(b, a % b, x, y)
  temp = x
  x = y
  y = temp - a // b * y
  return d

def liEu(a, b, c, x, y):
  d = ex_gcd(a, b, x, y)
  if c % d != 0:
      return 0
  k = c // d
  x = x * k
  y = y * k
  return 1
build本页面最近更新：2022/2/13 10:36:07，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：Enter-tainer, Great-designer, H-Shen, iamtwz, Ir1d, ksyx, kZime, leoleoasd, MegaOwIer, ouuan, Phemon, sshwy, stevebraveman, tsentau
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论