跳转至

裴蜀定理

什么是裴蜀定理？

裴蜀定理，又称贝祖定理。是代数几何中一个定理。

其内容是：

设 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. 由带余除法：

    \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}

    于是，有

    \gcd(a_1,b_1)=\gcd(b_1,r_1)=\gcd(r_1,r_2)=\cdots=(r_{n-1},r_n)=1

    故

    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.

应用

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）

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

评论