裴蜀定理

定义

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

其内容是：

设 是不全为零的整数，对任意整数 ，满足 ，且存在整数 , 使得 .

证明

对于第一点

由于

所以 ，其中 均为整数

因此

对于第二点

1. 若任何一个等于 , 则 . 这时定理显然成立。

2. 若 不等于 .

   由于 ,

   不妨设 都大于 ，.

   对 , 两边同时除以 , 可得 , 其中 .

   转证 .

   我们先回顾一下辗转相除法是怎么做的，由 我们把模出来的数据叫做 于是，有

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

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

   即

   由倒数第三个式子 代入上式，得

   然后用同样的办法用它上面的等式逐个地消去 ,

   可证得 . 这样等于是一般式中 的情况。

推广

逆定理

设 是不全为零的整数，若 是 的公因数，且存在整数 , 使得 ，则 。

特殊地，设 是不全为零的整数，若存在整数 , 使得 ，则 互质。

多个整数

裴蜀定理可以推广到 个整数的情形：设 是不全为零的整数，则存在整数 , 使得 。其逆定理也成立：设 是不全为零的整数， 是 的公因数，若存在整数 , 使得 ，则 。

应用

Codeforces Round #290 (Div. 2) D. Fox And Jumping

给出 张卡片，分别有 和 。在一条无限长的纸带上，你可以选择花 的钱来购买卡片 ，从此以后可以向左或向右跳 个单位。问你至少花多少元钱才能够跳到纸带上全部位置。若不行，输出 。

分析该问题，发现想要跳到每一个格子上，必须使得所选数 通过数次相加或相减得出的绝对值为 ，也即存在整数 使得 。由多个整数的裴蜀定理逆定理，这相当于从数组 选择若干个数，满足它们的最大公因数为 1，同时要求代价和最小。

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

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

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

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

设 表示考虑前 个数且最大公因数为 的最小代价，则有转移方程：

DP 后最终的总代价即为 。

如同一般的 0-1 背包问题，可以用滚动数组优化，去掉第一维。而这里 300 个数可达的最大公因数 是很稀疏的，因此还可以使用 unordered_map 代替数组储存下标 ，优化内存并进一步减少枚举量。

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

进一步结论

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

其中 和 为自然数。如果方程有解，称 可以被 、 表示。

记 。由 与 互素， 必然为奇数。则有结论：

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

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

证明

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

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

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

于是 也是非负整数。

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

反证法。若 有非负整数解 、，则：

由于 与 互素，所以 整除 ， 整除 ， 不超过 ， 不超过 。于是有：

矛盾！第二步证完。

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

由上可知，若 不可被表示，由于上述方程中已规定 在 到 之间，则 为负。所以：

显然 和 均非负，于是 可被表示。

几何意义

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

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

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

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

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

另一种解释

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

观察原方程， 的若干倍数 在 意义下互不相同。这些数恰好是这些最小值。那么当 时，小于等于 的能被表示的非负整数的数量是：

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

即 。

使用类欧几里得算法可以在 的时间内求解。因此我们得到了计算小于等于 的能被表示的非负整数的数量的工具。

题目

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

---

最后更新: 2024年8月14日
创建日期: 2018年8月30日