by Chesium 2021-10-26

前置知识

• [[裴蜀定理]]

扩展欧几里得算法

用于计算形如 $ax+by=m$ 的丢番图方程的整数解。 由裴蜀定理可知，该方程有整数解当且仅当 $\gcd(a,b)\mid m$，我们先求 $ax+by=\gcd(a,b)$ 的解，将求出的 $x$ 和 $y$ 乘上 $\frac{m}{\gcd(a,b)}$ 就是原方程的解了。 既然是“扩展欧几里得算法”，那肯定是从求最大公因数的欧几里得算法变化而来的：

int gcd(int a,int b){
 return b?gcd(b,a%b):a;
}

我们通过修改该算法，对每次递归的 $a_k$ 和 $b_k$ 逐次解 $a_kx+b_ky=\gcd(a,b)$ 即可最终解出 $ax+by=\gcd(a,b)$，先考虑递归边界，此时有 $b'=0$ ，$a'=\gcd(a,b)$ ，很显然有 $1\times a'+0\times b'=\gcd(a,b)$。即此时方程的解为 $x=1$ 和 $y=0$。 接着，假设我们解出了 $bx+(a\%b)y=\gcd(a,b)$ 的一个解为 $x=x'$ 及 $y=y'$ ，我们有：

我们令 $x=y'$ ， $y=x'-\lfloor\frac{a}{b}\rfloor y'$ ， 则就有 $ax+by=\gcd(a,b)$ 。这就是扩展欧几里得算法：

• 目的：输入 $a$ ， $b$ ，求出 $ax+by=m$ 的一组特解 $x_0$，$y_0$
• 判断：求出 $c=\frac{m}{\gcd(a,b)}$ ，若无法整除，则说明该方程没有整数解。
• 步骤：（递归）

1. 求出 $bx+(a\%b)y=\gcd(a,b)$ 的一组特解 $x'$，$y'$
2. 则有 $x_0=y'$ 且 $y_0=x'-\lfloor\frac{a}{b}\rfloor y'$
3. 递归边界： 递归到形如 $kx+0y=\gcd(a,b)$ 时，其的一组特解是 $x=1$ ， $y=0$（此时 $\gcd(a,b)=k$ ）
4. 最后要把 $x_0$，$y_0$ 乘上 $c$

求出特解 $x_0$，$y_0$ 后，怎么求出通解呢？ 设另一组解为 $x_1=x_0+\Delta x$ ，$y_1=y_0-\Delta y$ ，有：

即， $\Delta x$ 和 $\Delta y$ 的最小取值分别是 $d_x=\frac{b}{\gcd(a,b)}$ 和 $d_y=\frac{a}{\gcd(a,b)}$ ，$x$ 和 $y$ 以其作为周期。 接下来，我们想求 $x$ 和 $y$ 的最小非负整数值，这就是：

取模完一次后还要加上一个区间，因为可能 $x_0$ 、$y_0$ 是负数。最后又要取模一次，是为了处理 $x_0$ 、$y_0$ 是正数时重复加上区间，要回到原来最小的状态。 如果要求最小正整数解，那则要特判一下 $x_{min}$ 、 $y_{min}$ 为零的情况，此时最小正整数解就应为其区间。 同时，相应的，当 $x$ 取到最小值时 $y$ 取到最大值，反之亦然。 至于正整数解的个数，我们可以列出：

可以解得：

每一个 $k$ 的取值就对应着一个正整数解（加上等号就为非负整数解，修改不等式组右侧的值即可求出类似 “ $x>p$ 且 $y>q$ ” 这种解的个数）

要解形如

的一元线性同余方程，我们可以将方程变一下形：

这不就是要求一个关于 $x$ 和 $k$ 的丢番图方程的整数解吗？刚刚就讲了这个。 求乘法逆元是同理的。

总结：扩展欧几里得算法可以做以下的事：

• 求形如 $ax+by=\gcd(a,b)$ 不定方程的一组特解

通过额外的一些处理，其可以：

• 求解形如 $ax+by=c$ 的不定方程或形如 $ax\equiv b\ (\mathrm{mod}\ m)$ 的一元线性同余方程：
  • 有没有整数解
  • 解的通式
  • 正整数解或非负整数解的最大、最小值
  • 满足一定大小限制的解的数量

参考代码：（P5656 【模板】二元一次不定方程 (exgcd) - 洛谷)）

#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
//---//
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

typedef unsigned int u;
typedef long long ll;
typedef unsigned long long llu;

#define rep(i, a, b) for (ll i = a; i < b; i++)
#define REP(i, a, b) for (ll i = a; i <= b; i++)
#define per(i, b, a) for (ll i = b; i >= a; i--)

ll exgcd(ll a, ll b, ll &x, ll &y) {
  if (b) {
    ll g = exgcd(b, a % b, x, y);
    swap(x, y);
    y -= a / b * x;
    return g;
  } else {
    x = 1;
    y = 0;
    return a;
  }
}

signed main() {
  ll T, a, b, c, g, x0, y0, dx, dy, minx, miny, l, r;
  scanf("%lld", &T);
  while (T--) {
    scanf("%lld%lld%lld", &a, &b, &c);
    if (c % (g = exgcd(a, b, x0, y0)) == 0) {
      x0 *= c / g;
      y0 *= c / g;
      dx = b / g;
      dy = a / g;
      l = x0 % dx == 0 ? -x0 / dx + 1 : ceil(-(double)x0 / dx);
      r = y0 % dy == 0 ? y0 / dy - 1 : floor((double)y0 / dy);
      if (l <= r)
        printf("%lld %lld %lld %lld %lld\n", r - l + 1, x0 + l * dx,
               y0 - r * dy, x0 + r * dx, y0 - l * dy);
      else {
        minx = (x0 % dx + dx) % dx;
        if (minx == 0) minx = dx;
        miny = (y0 % dy + dy) % dy;
        if (miny == 0) miny = dy;
        printf("%lld %lld\n", minx, miny);
      }
    } else
      printf("-1\n");
  }
}

// https://www.luogu.com.cn/record/60967484

参考代码：（P2613 【模板】有理数取余 - 洛谷)）

#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
//---//
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

typedef unsigned int u;
typedef long long ll;
typedef unsigned long long llu;

#define rep(i, a, b) for (ll i = a; i < b; i++)
#define REP(i, a, b) for (ll i = a; i <= b; i++)
#define per(i, b, a) for (ll i = b; i >= a; i--)

const ll mod = 19260817;

ll read() {
  ll r = 0;
  char c = getchar();
  while (c < '0' || c > '9') c = getchar();
  while (c >= '0' && c <= '9') {
    r = (r * 10 + c - '0') % mod;
    c = getchar();
  }
  return r;
}

void exgcd(ll a, ll b, ll& x, ll& y) {
  if (b) {
    exgcd(b, a % b, x, y);
    swap(x, y);
    y -= a / b * x;
  } else {
    x = 1;
    y = 0;
  }
}

signed main() {
  ll a = read(), b = read(), x, y;
  if (b == 0) return 1 & printf("Angry!");
  exgcd(b, mod, x, y);
  printf("%lld", (x % mod + mod) % mod * a % mod);
}

// https://www.luogu.com.cn/record/60970838