数论：不定方程整数解

欧几里得算法

又称辗转相除法，迭代求两数 gcd。

由 $(a, b) = (a, ka + b)$ 的性质，$\gcd(a, b) = \gcd(b, a\bmod b)$。容易证明这么做的复杂度是 $O(\log n)$。

注意：$\gcd(0, a) = a$。

裴蜀定理

裴蜀定理：设 $(a, b) = d$，则对任意整数 $x, y$，有 $d|(ax + by)$ 成立；特别地，一定存在 $x, y$ 满足 $ax + by = d$。

等价的表述：不定方程 $ax + by = c(a, b, c 为整数)$ 有解的充要条件为 $(a, b)|c$。

P4549 【模板】裴蜀定理

裴蜀定理可以推广到多元方程。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    
    int n; scanf("%d", &n); int a; scanf("%d", &a); int g = a; 
    for(int i=2; i<=n; ++i) {
        scanf("%d", &a); if(a == 0) continue;
        if(a < 0) a = -a;
        g = __gcd(g, a);
    }
    printf("%d\n", g);
    return 0;
}

扩展欧几里得（exgcd）

裴蜀定理的推论：$a, b$ 互质等价于 $ax + by = 1$ 有解。

因此，要求不定方程 $ax+by=c$ 的解，只需求 $ax+by=d,d=\gcd(a,b)$ 的解，然后扩倍（乘上 $\frac{c}{d}$）即可。

求出任意一个解

考虑使用欧几里德算法的思想，令 $a = bq + r$，其中 $r = a \bmod b$，递归求出 $bx + ry = d$ 的一个解。

设求出 $bx + ry = d$ 的一个解为 $x = x_0, y = y_0$，考虑如何把它变形成 $ax + by = d$ 的解。

将 $a = bq + r$ 代入 $ax + by = d$，化简得

$$
b(xq + y) + rx = d
$$

令
$$
xq + y = x_0, x = y_0
$$
上式成立。

故
$$
x = y_0, y = x_0 - y_0q
$$
为 $ax + by = d$ 的解。

注意边界情况：当 $b = 0$ 时，必有 $a = d$，此时令 $x = 1, y = 0$ 即可。

怎么求出所有解？

先用exgcd 求出任意一个解 $x = x_0, y = y_0$，再求出 $ax + by = 0$ 的最小的解
$$
x = dx = b/(a, b), y = dy = -a/(a, b)
$$
所有解就是
$$
x = x_0 + kdx, y = y_0 + kdy,k\in \mathbb{Z}
$$

P1082 同余方程

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
ll a, b;
pll exgcd(ll a, ll b) {
    if(b == 0) return {1,0};
    pll p = exgcd(b, a%b);
    return {p.second, p.first-a/b*p.second};
}

int main() {
    
    scanf("%lld%lld", &a, &b);
    ll x = exgcd(a,b).first;
    while(x < 0) x+=b;
    while(x-b > 0) x-=b;
    printf("%lld\n", x);
    return 0;
}

P3951 [NOIP2017提高组]小凯的疑惑

方法很多，这里提供一个比较好理解的扩欧做法。

首先已知题目必存在答案，那么设答案为 $k-1$ ，则 $ax+by=k$ 必有一组非负整数解 $(x,y)$

假设 $ax+by=k-1$ 有非负整数解，那么该式必能化为

$$
a(x-x_0)+b(y-y_0)=k
$$
其中
$$
ax_0+by_0=1
$$

注意到，若尽量使该式能够有解，则有两种情况，分别令 $x_0$ 或 $y_0$ 取其最小非负整数解 $x’$ 和 $y’'$（因为一方最小时另一方必为最大情况）

因此为了让原式无解，需保证 $x-x’<0, y-y’‘<0$，即 $x<x’,y<y’'$

因为要构造最大非负整数解，所以令 $x=x’-1,y=y’‘-1$ 所得即为 $k$，答案即为 $a(x’-1)+b(y’'-1)-1$，就可以直接利用扩欧求解了。

不过其实还能进一步化简

有一个很显然的结论，$ax_0+by_0=1$ 是没有非负整数解的

然后把 $x,y$ 想象成分别在两个竖直的数轴上，可以发现，对于上面的两组解 $(x’,y’),(x’‘,y’')$，他们都是离水平面（原点）最近的解，所以他们在扩欧通解上是两组相邻的解

则

$$
\begin{aligned}
ans&=k-1\\
&=a(x’-1)+b(y’‘-1)-1 \\
&=ax’-a+by’‘-b-1 \\
&=ax’+by’+ab-a-b-1 \\
&=ab-a-b.
\end{aligned}
$$