裴蜀定理 & 一次不定方程

设 $a,b$ 是不全为零的整数。那么，对于任意整数 $x,y$，都有 $gcd(a,b)\mid ax+by$ 成立；而且，存在整数 $x,y$，使得 $ax+by=gcd(a,b)$ 成立。

记 $d=gcd(a,b)$。因为 $d\mid a,b$，所以，存在整数 $u,v$ 使得 $a=du,b=dv$ 成立。因此，总有

$$ax+by=d(au+bv).$$

这就说明 $d\mid ax+by$。

反过来，需要说明存在 $x,y$ 使得等式成立。如果 $a,b$ 之一是 $0$，不妨设 $b=0$，那么它们的最大公约数为 $d=a$，显然有 $(x,y)=(1,0)$ 使得等式成立。接下来，考虑 $a,b$ 均不为零的情形。由于 $gcd(a,b)=gcd(-a,b)=gcd(a,-b)$，所以不妨设 $a,b$ 都是正数。

考虑辗转相除法的过程，有

$$\begin{array}{rlrl}a& =q_{1}b+r_1,& & 0\le r_1<b,\\ b& =q_2{r}_1+r_2,& & 0\le r_2<r_1,\\ r_1& =q_3{r}_2+r_3,& & 0\le r_3<r_2,\\ & \cdots \\ r_{n-3}& =q_{n-1}{r}_{n-2}+r_{n-1},& & 0\le r_{n-1}<r_{n-2},\\ r_{n-2}& =q_n{r}_{n-1}+r_n,& & 0\le r_n<r_{n-1},\\ r_{n-1}& =q_{n+1}{r}_n.\end{array}$$

由于最大公约数是 $d$，最后一步辗转相除时，一定有 $r_n=d$。所以，倒数第二个等式可以写作

$$d=r_n=r_{n-2}-q_n{r}_{n-1}.$$

从倒数第三个等式中解出

$$r_{n-1}=r_{n-3}-q_{n-1}{r}_{n-2}$$

再代入上式，就可以消去 $r_{n-1}$：

$$\begin{array}{rl}d& =r_{n-2}-q_n(r_{n-3}-q_{n-1}{r}_{n-2})\\ & =(1+q_n{q}_{n-1})r_{n-2}-q_n{r}_{n-3}.\end{array}$$

类似地，可以逐步地消去所有 $r_{n-2},r_{n-3},\cdots ,r_2,r_1$，最终得到

$$d=xa+yb.$$

这就证明了存在 $x,y$ 使得 $ax+by=d$ 成立。由前文分析可知，这也证明了原命题。

整数 $a,b$ 互素，当且仅当存在整数 $x,y$，使得 $ax+by=1$ 成立。

设 $a_1,a_2,\cdots ,a_n$ 是不全为零的整数。那么，对于任意整数 $x_1,x_2,\cdots ,x_n$，都有 $gcd(a_1,a_2,\cdots ,a_n)\mid a_1{x}_1+a_2{x}_2+\cdots +a_n{x}_n$ 成立；而且，存在整数 $x_1,x_2,\cdots ,x_n$，使得 $gcd(a_1,a_2,\cdots ,a_n)=a_1{x}_1+a_2{x}_2+\cdots +a_n{x}_n$ 成立。

利用 $gcd(a_1,a_2,\cdots ,a_n)=gcd(gcd(a_1,a_2,\cdots ,a_{n-1}),a_n)$ 这一点，对 $n$ 进行归纳即可。

分析该问题，发现想要跳到每一个格子上，必须使得所选数 $l_{i_1},\cdots ,l_{i_k}$ 通过数次相加或相减得出的绝对值为 $1$。也就是说，存在整数 $x_1,\cdots ,x_k$ 使得 $l_{i_1}{x}_1+\cdots +l_{i_k}{x}_k=1$。由多个整数的裴蜀定理，这相当于从数组 $l_1,\cdots ,l_n$ 中选择若干个数，满足它们的最大公约数为 $1$，同时要求代价和最小。

解法 1：将最小代价和看作是最短路径问题，可以用 Dijkstra 算法求解。图的顶点处存储了当前的最大公约数的取值。图的起点是 $0$，要到达的目标点是 $1$。每走一步，就从当前顶点 $x$ 出发，沿着长度为 $c_i$ 的边走到顶点 $gcd(x,l_i)$。这一算法的时间复杂度为 $O(n^2\log n)$。

解法 2：从数组 $l_1,\cdots ,l_n$ 选择若干个数，满足它们的最大公因数为 $1$，且代价和最小，由此可以想到 0-1 背包问题。

设 $f_{i,j}$ 表示考虑前 $i$ 个数且最大公因数为 $j$ 的最小代价，则有转移方程：

$$f_{i,j}=\underset{gcd(k,l_i)=j}{min}{f}_{i-1,k}+c_i.$$

DP 后最终的总代价即为 $f_{n,1}$。

如同一般的 0-1 背包问题，可以用滚动数组优化，去掉第一维。而这里 300 个数可以组成的最大公约数 $j$ 是很稀疏的，可以用哈希表储存。

实际上，这里解法 1 建出的图便是解法 2 中动态规划的状态转移图，解法 2 相当于用动态规划求有向无环图的最短路，因此解法 1 和解法 2 是等价的。但解法 2 无需储存全图，同时 DP 的时间复杂度为 $O(n+m)$，相比 Dijkstra 算法更低，因此解法 2 在时间和空间上更优。

对于互素的正整数 $a_1,a_2$，不能够写作 $a_1{x}_1+a_2{x}_2(x_1,x_2\in \mathbf{N})$ 的最大整数是 $C=a_1{a}_2-a_1-a_2$。而且，对于所有 $k\in \mathbf{Z}$，整数 $k$ 和 $C-k$ 中有且只有一个可以写作该形式。

由于 $a_1,a_2$ 互素，对于任意整数 $k$，方程 $a_1{x}_1+a_2{x}_2=k$ 一定有解，且通解为

$$(x_1,x_2)=(x_1^{\circ }+t{a}_2,x_2^{\circ }-t{a}_1).(t\in \mathbf{Z})$$

取 $t$ 为 $x_2^{\circ }$ 对 $a_1$ 作带余除法得到的商，那么，余数 $x_2=x_2^{\circ }-t{a}_1$ 位于 $0$ 和 $a_1-1$ 之间。考察此时得到的一组解 $(x_1,x_2)$。因为 $x_2$ 是它能够取到的最小非负整数值，所以 $n$ 可表示当且仅当 $x_1\ge 0$。

第一步：证明大于 $C$ 的整数都是可表示的。

当 $k>C$ 时，有

$$a_1{x}_1=k-a_2{x}_2>C-a_2(a_1-1)=-a_1.$$

所以，$x_1>-1$，也就是说，$x_1\ge 0$。这说明，$(x_1,x_2)$ 是一组自然数解。此时，$k$ 可以写作所求形式。

第二步：证明 $C$ 不可表示。进而，$C$ 是最大的不可表示的整数，且 $k$ 和 $C-k$ 并非都可表示的。

反证法。假设 $C$ 可以表示，即存在 $x_1,x_2\in \mathbf{N}$ 使得 $a_1{x}_1+a_2{x}_2=C$ 成立。代入 $C$ 的表达式，可知

$$a_1{a}_2=a_1(x_1+1)+a_2(x_2+1).$$

因此，$a_2\mid (x_1+1)$ 且 $a_1\mid (x_2+1)$。又因为 $x_1+1,x_2+1$ 都是正数，所以，有

$$a_1{a}_2\ge a_1{a}_2+a_2{a}_1=2a_1{a}_2.$$

矛盾。这就说明 $C$ 不可表示。结合第一步，它也就是不可表示的最大整数。

如果 $k$ 和 $C-k$ 都可以表示，那么，将 $k$ 和 $C-k$ 的表示中的系数相加就得到 $C$ 的表示中的系数，这与 $C$ 不可表示矛盾，故而 $k$ 和 $C-k$ 至多只有一个可以表示。

第三步：证明如果 $k$ 不可表示，那么 $C-k$ 一定是可表示的。

设 $(x_1,x_2)$ 是前文所设的方程 $a_1{x}_1+a_2{x}_2=k$ 的整数解。那么，前文已经说明 $k$ 不可表示，就等价于 $x_1<0$。因此，有

$$C-k=a_1{a}_2-a_1-a_2-a_1{x}_1-a_2{x}_2=a_1(-1-x_1)+a_2(a_1-1-x_2).$$

其中，$-1-x_1$ 和 $a_1-1-x_2$ 都是非负整数，所以，$C-k$ 可以表示。

此处仅证明 $C=a_1{a}_2-a_1-a_2$ 是最大的不可表示的自然数，其余部分的证明类似证明一。

考虑模 $a_2$ 意义下，每个剩余系中最小的可表示的自然数。因为同一个剩余系中的不同自然数可以通过加减若干个 $a_2$ 互相转化，所以，在讨论最小可表示数时，只需要考虑加减 $a_1$ 的可能性就可以了。由于 $a_1$ 和 $a_2$ 互素，所以，每个剩余系中最小的可表示的自然数恰好就是 $a_1$ 的倍数

$$0,a_1,2a_1,\cdots ,(a_2-1)a_1.$$

因此，最大的不可表示数为

$$\underset{0\le i<a_2}{max}i{a}_1-a_2=(a_2-1)a_1-a_2=C.$$