裴蜀定理

定义

裴蜀定理，又称贝祖定理（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\)

对于第二点

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

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

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

对 \(ax+by=d\), 两边同时除以 \(d\), 可得 \(a_1x+b_1y=1\), 其中 \((a_1,b_1)=1\).

转证 \(a_1x+b_1y=1\).

我们先回顾一下辗转相除法是怎么做的，由 \(\gcd(a, b) \rightarrow \gcd(b,a\mod b) \rightarrow \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{aligned}a_1 &= q_1b_1+r_1 &(0\leq r_1<b_1) \\ b_1 &= q_2r_1+r_2 &(0\leq r_2<r_1) \\ r_1 &= q_3r_2+r_3 &(0\leq r_3<r_2) \\ &\cdots \\ r_{n-3} &= q_{n-1}r_{n-2}+r_{n-1} \\ r_{n-2} &= q_nr_{n-1}+r_n \\ r_{n-1} &= q_{n+1}r_n\end{aligned} \]

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

\[ r_{n-2}=x_nr_{n-1}+1 \]

即

\[ 1=r_{n-2}-x_nr_{n-1} \]

由倒数第三个式子 \(r_{n-1}=r_{n-3}-x_{n-1}r_{n-2}\) 代入上式，得

\[ 1=(1+x_nx_{n-1})r_{n-2}-x_nr_{n-3} \]

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

可证得 \(1=a_1x+b_1y\). 这样等于是一般式中 \(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)\)。

应用

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

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

分析该问题，发现想要跳到每一个格子上，必须使得所选数 \(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} = \min_{\gcd(k, l_i) = j} 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{cases}x=x_0+bt\\y=y_0-at\end{cases} \]

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

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

\[ ax=n-by>ab-a-b-by\geqslant 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)\geqslant 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\) 在 \(\pmod b\) 意义下互不相同。这些数恰好是这些最小值。那么当 \(n<ab\) 时，小于等于 \(n\) 的能被表示的非负整数的数量是：

\[ \sum\limits_{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 省买不到的数目

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用