题解 P4549 【【模板】裴蜀定理】

· · 题解

这道题写的是Bézout定理，不过可能要用到一个最大公约数理论的定理：

设a_1,\cdots ,a_i是不全为0的整数，有\gcd(a_1,\cdots,a_i) = \min(s = a_1x_1+\cdots+a_ix_i)其中x_j \in \mathbb{Z}(1 \le j \le i), s > 0，即\gcd(a_1,\cdots ,a_i)等于a_1,\cdots ,a_i的所有整系数线性组合组成的集合中的最小正整数。

给出一个可能不太完备的证明（引用的部分是对这句证明的解释）：

设S表示a_1,\cdots ,a_i的所有整系数线性组合组成的集合，则S中必有一个最小的正整数，设为s_0。

对a_1,\cdots ,a_i的任一个公约数d，都有d \mid s_0，所以|d| \le s_0。即s_0不小于a_1,\cdots ,a_i的任一个公约数。

因为d是a_1,\cdots ,a_i的公约数，所以必然能整除a_1,\cdots ,a_i的所有线性组合。

对任意a_j，设a_j = q_js_0 + r_j，其中0 \le r_j < s_0，则有r_j \in S。

因为a_j \in S，s_0 \in S，且有r_j = a_j - q_js_0，所以a_j和s_0的线性组合r_j \in S。

若r_j>0，则与s_0是S中最小的正整数矛盾，所以r_j=0，即s_0 \mid a_j。也即s_0是a_1,\cdots,a_i的公约数。

所以s_0 = \gcd(a_1,\cdots,a_i)。

\mathcal{Q.E.D}

这个定理在一些数论书上能够见到（比如《初等数论》）。

所以这道题只需要求一下所有数字的\gcd就好啦。代码就不放了。