扩展欧几里得算法

根据以下两个定理，可以求出线性同余方程 $ax\equiv b \pmod n$ 的解。

定理 1：线性同余方程 $ax\equiv b \pmod n$ 可以改写为如下线性不定方程：

$$ax + nk = b$$

其中 $x$ 和 $k$ 是未知数。这两个方程是等价的，有整数解的充要条件为 $\gcd(a,n) \mid b$。

应用扩展欧几里德算法可以求解该线性不定方程。根据定理 1，对于线性不定方程 $ax+nk=b$，可以先用扩展欧几里得算法求出一组 $x_0,k_0$，也就是 $ax_0+nk_0=\gcd(a,n)$，然后两边同时除以 $\gcd(a,n)$，再乘 $b$。就得到了方程

$$a\dfrac{b}{\gcd(a,n)}x_0+n\dfrac{b}{\gcd(a,n)}k_0=b$$

于是找到方程的一个解。

定理 2：若 $\gcd(a,n)=1$，且 $x_0$、$k_0$ 为方程 $ax+nk=b$ 的一组解，则该方程的任意解可表示为：

$$x=x_0+nt$$

$$k=k_0-at$$

并且对任意整数 $t$ 都成立。

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

$$x=(x \bmod t+t) \bmod t$$

其中有

$$t=\dfrac{n}{\gcd(a,n)}$$

如果仔细考虑，用扩展欧几里得算法求解与用逆元求解，两种方法是等价的。

实现

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 false;
  int k = c / d;
  x *= k;
  y *= k;
  return true;
}