WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
数学部分简介
符号
复数
位运算
快速幂
进位制
高精度计算
平衡三进制
素数
最大公约数
欧拉函数
筛法
欧拉定理 & 费马小定理
类欧几里德算法
裴蜀定理
乘法逆元
线性同余方程
中国剩余定理
二次剩余
BSGS
原根
卢卡斯定理
莫比乌斯反演
杜教筛
Min_25 筛
分解质因数
多项式部分简介
拉格朗日插值
快速傅里叶变换
快速数论变换
快速沃尔什变换
多项式求逆
多项式开方
多项式除法|取模
多项式对数函数|指数函数
多项式牛顿迭代
多项式多点求值|快速插值
多项式三角函数
多项式反三角函数
常系数齐次线性递推
生成函数简介
普通生成函数
指数生成函数
向量
矩阵
高斯消元
线性基
线性规划简介
单纯形算法
排列组合
卡特兰数
斯特林数
贝尔数
伯努利数
康托展开
容斥原理
抽屉原理
概率初步
置换群
斐波那契数列
博弈论
牛顿迭代法
数值积分
分段打表
64 objects
本站非官方,所收集资源均来源于网络。
裴蜀定理 - 数学
## 什么是裴蜀定理? 裴蜀定理,又称贝祖定理(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
给出 $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](/lang/csl/associative-container/) )