Bezout's Theorem

什么是裴蜀定理？

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

其内容是：

设 a,b 是不全为零的整数，则存在整数 x,y , 使得 ax+by=\gcd(a,b) .

证明

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

  2. 若 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）

buildLast update and/or translate time of this article，Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article OI-wiki
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

Comments