裴蜀定理

定义

裴蜀定理，又称贝祖定理（Bézout's lemma）、贝祖等式（Bézout's identity）。是一个关于最大公约数的定理。

其内容是：

设 $a,b$ 是不全为零的整数，对任意整数 $x,y$，满足 $gcd(a,b)\mid ax+by$，且存在整数 $x,y$, 使得 $ax+by=gcd(a,b)$.

证明

对于第一点

由于 $gcd(a,b)\mid a,gcd(a,b)\mid b$

所以 $gcd(a,b)\mid ax,gcd(a,b)\mid by$，其中 $x,y$ 均为整数

因此 $gcd(a,b)\mid ax+by$

对于第二点

1. 若任何一个等于 $0$, 则 $gcd(a,b)=a$. 这时定理显然成立。

2. 若 $a,b$ 不等于 $0$.

   由于 $gcd(a,b)=gcd(a,-b)$,

   不妨设 $a,b$ 都大于 $0$，$a\ge b,gcd(a,b)=d$.

   对 $ax+by=d$, 两边同时除以 $d$, 可得 $a_{1}x+b_{1}y=1$, 其中 $(a_1,b_1)=1$.

   转证 $a_{1}x+b_{1}y=1$.

   我们先回顾一下辗转相除法是怎么做的，由 $gcd(a,b)\to gcd(b,a\mathrm{mod}b)\to \dots$ 我们把模出来的数据叫做 $r$ 于是，有

   $$gcd(a_1,b_1)=gcd(b_1,r_1)=gcd(r_1,r_2)=\cdots =(r_{n-1},r_n)=1$$

   把辗转相除法中的运算展开，做成带余数的除法，得

   $$\begin{array}{rlr}{a}_1& =q_1{b}_1+r_1& (0\le r_1<b_1)\\ b_1& =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}\\ r_{n-2}& =q_n{r}_{n-1}+r_n\\ r_{n-1}& =q_{n+1}{r}_n\end{array}$$

   不妨令辗转相除法在除到互质的时候退出则 $r_n=1$ 所以有（$q$ 被换成了 $x$，为了符合最终形式）

   $$r_{n-2}=x_n{r}_{n-1}+1$$

   即

   $$1=r_{n-2}-x_n{r}_{n-1}$$

   由倒数第三个式子 $r_{n-1}=r_{n-3}-x_{n-1}{r}_{n-2}$ 代入上式，得

   $$1=(1+x_n{x}_{n-1})r_{n-2}-x_n{r}_{n-3}$$

   然后用同样的办法用它上面的等式逐个地消去 $r_{n-2},\cdots ,r_1$,

   可证得 $1=a_{1}x+b_{1}y$. 这样等于是一般式中 $d=1$ 的情况。

推广

逆定理

设 $a,b$ 是不全为零的整数，若 $d>0$ 是 $a,b$ 的公因数，且存在整数 $x,y$, 使得 $ax+by=d$，则 $d=gcd(a,b)$。

特殊地，设 $a,b$ 是不全为零的整数，若存在整数 $x,y$, 使得 $ax+by=1$，则 $a,b$ 互质。

多个整数

裴蜀定理可以推广到 $n$ 个整数的情形：设 $a_1,a_2,\dots ,a_n$ 是不全为零的整数，则存在整数 $x_1,x_2,\dots ,x_n$, 使得 $a_1{x}_1+a_2{x}_2+\cdots +a_n{x}_n=gcd(a_1,a_2,\dots ,a_n)$。其逆定理也成立：设 $a_1,a_2,\dots ,a_n$ 是不全为零的整数，$d>0$ 是 $a_1,a_2,\dots ,a_n$ 的公因数，若存在整数 $x_1,x_2,\dots ,x_n$, 使得 $a_1{x}_1+a_2{x}_2+\cdots +a_n{x}_n=d$，则 $d=gcd(a_1,a_2,\dots ,a_n)$。

应用

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

解法 1：我们可以转移思想，因为这些数互质，即为 $0$ 号节点开始，每走一步求 $gcd$（节点号，下一个节点），同时记录代价（求边权），就成为了从 $0$ 通过不断 $gcd$ 最后变为 $1$ 的最小代价。

由于：互质即为最大公因数为 $1$，$gcd(0,x)=x$ 这两个定理，可以证明该算法的正确。选择优先队列优化 Dijkstra 求解。

不过还有个问题，即为需要记录是否已经买过一个卡片，开数组标记由于数据范围达到 ${10}^9$ 会超出内存限制，可以想到使用 unordered_map（比普通的 map 更快地访问各个元素，迭代效率较低，详见 STL-map）

解法 2：从数组 $l_1,\dots ,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$ 是很稀疏的，因此还可以使用 unordered_map 代替数组储存下标 $j$，优化内存并进一步减少枚举量。

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

进一步结论

对自然数 $a$、$b$ 和整数 $n$，$a$ 与 $b$ 互素，考察不定方程：

$$ax+by=n$$

其中 $x$ 和 $y$ 为自然数。如果方程有解，称 $n$ 可以被 $a$、$b$ 表示。

记 $C=ab-a-b$。由 $a$ 与 $b$ 互素，$C$ 必然为奇数。则有结论：

对任意的整数 $n$，$n$ 与 $C-n$ 中有且仅有一个可以被表示。

即：可表示的数与不可表示的数在区间 $[0,C]$ 对称（关于 $C$ 的一半对称）。$0$ 可被表示，$C$ 不可被表示；负数不可被表示，大于 $C$ 的数可被表示。

证明

由于 $a$、$b$ 互素，因此原方程有整数解。设解为：

$$\{\begin{array}{l}x=x_0+bt\\ y=y_0-at\end{array}$$

其中 $t$ 为整数。取适当的 $t$，使得 $y$ 位于 $0$ 到 $a-1$ 之间。这只需在 $y_0$ 上加上或减去若干个 $a$，即可得到这样的 $t$。

第一步：证明大于 $C$ 的数都可以被表示。当 $n$ 大于 $C$ 时：

$$ax=n-by>ab-a-b-by⩾ab-a-b-b(a-1)=-a$$

于是 $x$ 也是非负整数。

第二步：证明 $C$ 不可被表示，进而 $n$ 与 $C-n$ 不可能都被表示。

反证法。若 $ax+by=ab-a-b$ 有非负整数解 $x$、$y$，则：

$$ab=a(x+1)+b(y+1)$$

由于 $a$ 与 $b$ 互素，所以 $a$ 整除 $y+1$，$b$ 整除 $x+1$，$a$ 不超过 $y+1$，$b$ 不超过 $x+1$。于是有：

$$ab=a(x+1)+b(y+1)⩾ab+ab=2ab$$

矛盾！第二步证完。

第三步：证明如果 $n$ 不可被表示，则 $C-n$ 可被表示。

由上可知，若 $n$ 不可被表示，由于上述方程中已规定 $y$ 在 $0$ 到 $a-1$ 之间，则 $x$ 为负。所以：

$$ab-a-b-ax-by=a(-x-1)+b(a-1-y)$$

显然 $-x-1$ 和 $a-1-y$ 均非负，于是 $C-n$ 可被表示。

几何意义

重新观察方程 $ax+by=n$，将它看成一条直线。直线与两坐标轴在第一象限围成三角形。

当 $n<ab$ 的时候，这个直线在第一象限，至多只能通过一个整点。

根据上述讨论：当 $n$ 可以被表示的时候，直线恰好经过一个整点；当 $n$ 不可以被表示的时候，直线不经过整点（在第一象限）。

这结论也可以理解为：作三角形 $(0,0)(b,0)(0,a)$。随着 $n$ 从 $0$ 不断增加，直线向右上方平移，整点会一个一个地通过直线，直到最后才撞上两个整点。

因此，小于等于 $n$ 的能被表示的非负整数的数量，恰好就是直线 $ax+by=n$（含）与两坐标轴（含）在第一象限围成三角形覆盖的整点个数。

另一种解释

考虑模 $b$ 意义下每个剩余系中最小能被表示的值是多少——大于他们的可以通过增加若干个 $b$ 得到。

观察原方程，$a$ 的若干倍数 $0,a,\cdots ,(b-1)a$ 在 $(\mathrm{mod}b)$ 意义下互不相同。这些数恰好是这些最小值。那么当 $n<ab$ 时，小于等于 $n$ 的能被表示的非负整数的数量是：

$$\sum _{i=0}^{\left[\frac{n}{a}\right]}\left[\frac{n-ia}{b}\right]$$

这是一个非常经典的直线下整点问题，恰好是这条直线：

$$y=-\frac{a}{b}x+\frac{n}{b}$$

即 $ax+by=n$。

使用类欧几里得算法可以在 $O(\log max(a,b))$ 的时间内求解。因此我们得到了计算小于等于 $n$ 的能被表示的非负整数的数量的工具。

题目

P3951 NOIP2017 提高组 小凯的疑惑/蓝桥杯 2013 省 买不到的数目

本页面最近更新：2024/8/14 17:52:13，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：ylxmf2005, buggg-hfc, Great-designer, greyqz, iamtwz, ImpleLee, Ir1d, MegaOwIer, monkeysui, ShizuhaAki, sshwy, Sunlight-zero, TianKong-y, Tiphereth-A, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用