跳转至

裴蜀定理

定义

裴蜀定理,又称贝祖定理(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 省 买不到的数目