一个二级结论

偶遇一算法题，原题链接，题干可简化为：

已知两个数m和n，m和n互素，求不能由这两个数线性表达（\(C = an + bm\),其中a,b均是自然数）的最大的整数\(L\)。

提出结论：不可能有：\(L > nm - n - m\)。即：当\(C > nm + n + m\)时，一定有\(an+bm\)型表示。

该结论能极大程度上减少循环次数，降低本题难度。

证明如下：

首先先提出两个引理：

（1）裴蜀定理：当a和b互素时，一定有（u，v）整数对满足：\(au+bv = 1\);

（2）对于任意的整数a，一定有唯一的整数t，使得：\(x = a + bt,0 \leq x \leq b-1\)。这个引理的证明非常简单，结合周期性和取mod的思想非常显然。

假设\(C > nm - n - m\)，由于裴蜀定理：有（u，v）使得：\(nu+mv = 1\)，那么有：\(\(n(Cu)+m(Cv) = C\)\)

下面取：\(a = Cu + mt\)，由于引理（2），很显然得出：一定存在\(t\)，使得：\(0 \leq a \leq m-1\)；

那么，相应地，取：\(b = Cv - nt\)，于是有：

于是，只要证明：\(0 \leq b\)即可，而：显然\(b \in Z\)

那么只要证明：\(b > -1\)

而

综上，证毕 \(\square\)

证明启发自[elEvenxue]

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