裴蜀定理
裴蜀定理,又称贝祖定理(Bézout's lemma)。是一个关于最大公约数的定理。
其内容是:
设 a,b 是不全为零的整数,则存在整数 x,y, 使得 ax+by=\gcd(a,b).
证明¶
-
若任何一个等于 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 ... 我们把模出来的数据叫做 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+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 的情况。
应用¶
Codeforces Round #290 (Div. 2) D. Fox And Jumping
给出 n 张卡片,分别有 l_i 和 c_i。在一条无限长的纸带上,你可以选择花 c_i 的钱来购买卡片 i,从此以后可以向左或向右跳 l_i 个单位。问你至少花多少元钱才能够跳到纸带上全部位置。若不行,输出 -1。
分析该问题,先考虑两个数的情况,发现想要跳到每一个格子上,必须使得这些数通过数次相加或相减得出的绝对值为 1,进而想到了裴蜀定理。
可以推出:如果 a 与 b 互质,那么一定存在两个整数 x 与 y,使得 ax+by=1.
由此得出了若选择的卡牌的数通过数次相加或相减得出的绝对值为 1,那么这些数一定互质,此时可以考虑动态规划求解。
不过可以转移思想,因为这些数互质,即为 0 号节点开始,每走一步求 \gcd(节点号,下一个节点),同时记录代价,就成为了从 0 通过不断 \gcd 最后变为 1 的最小代价。
由于:互质即为最大公因数为 1,\gcd(0,x)=x 这两个定理,可以证明该算法的正确。选择优先队列优化 Dijkstra 求解。
不过还有个问题,即为需要记录是否已经买过一个卡片,开数组标记由于数据范围达到 10^9 会超出内存限制,可以想到使用 unordered_map
(比普通的 map
更快地访问各个元素,迭代效率较低,详见 STL-map)
进一步结论¶
设自然数 a、b 和整数 n。a 与 b 互素。考察不定方程:
其中 x 和 y 为自然数。如果方程有解,称 n 可以被 a、b 表示。
记 C=ab-a-b。由 a 与 b 互素,C 必然为奇数。则有结论:
对任意的整数 n,n 与 C-n 中有且仅有一个可以被表示。
即:可表示的数与不可表示的数在区间 [0,C] 对称(关于 C 的一半对称)。0 可被表示,C 不可被表示;负数不可被表示,大于 C 的数可被表示。
证明¶
由于 a、b 互素,因此原方程有整数解。设解为:
其中 t 为整数。取适当的 t,使得 y 位于 0 到 a-1 之间。这只需在 y_0 上加上或减去若干个 a,即可得到这样的 t。
第一步:证明大于 C 的数都可以被表示。当 n 大于 C 时:
于是 x 也是非负整数。
第二步:证明 C 不可被表示,进而 n 与 C-n 不可能都被表示。
反证法。若 ax+by=ab-a-b 有非负整数解 x、y,则:
由于 a 与 b 互素,所以 a 整除 y+1,b 整除 x+1,a 不超过 y+1,b 不超过 x+1。于是有:
矛盾!第二步证完。
第三步:证明如果 n 不可被表示,则 C-n 可被表示。
由上可知,若 n 不可被表示,由于上述方程中已规定 y 在 0 到 a-1 之间,则 x 为负。所以:
显然 -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,···, (b−1)a 在 \pmod b 意义下互不相同。这些数恰好是这些最小值。那么当 n<ab 时,小于等于 n 的能被表示的非负整数的数量是:
这是一个非常经典的直线下整点问题,恰好是这条直线:
即 ax+by=n。
使用类欧几里得算法可以在 O(\log \max(a,b)) 的时间内求解。因此我们得到了计算小于等于 n 的能被表示的非负整数的数量的工具。
题目¶
P3951 NOIP2017 提高组 小凯的疑惑/蓝桥杯 2013 省 买不到的数目
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用