差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:namespace:裴蜀定理与一次不定方程 [2020/05/11 22:11]
great_designer [小于等于K 的能被表示的非负整数的数量]
+++ 2020-2021:teams:namespace:裴蜀定理与一次不定方程 [2020/05/11 22:56] (当前版本)
great_designer [著名结论]
@@ 行 11: / 行 11: @@
 其中x和y为自然数。如果方程有解，称n可以被a、b表示。
-记A=ab-a-b。由a与b互素，A必然为奇数。则有结论：
+记C=ab-a-b。由a与b互素，C必然为奇数。则有结论：
-**对任意的整数n，n与A-n中有且仅有一个可以被表示。**
+**对任意的整数n，n与C-n中有且仅有一个可以被表示。**
-即：可表示的数与不可表示的数在区间[0,A]对称（关于A的一半对称）。0可被表示，A不可被表示；负数不可被表示，大于A的数可被表示。
+即：可表示的数与不可表示的数在区间[0,C]对称（关于C的一半对称）。0可被表示，C不可被表示；负数不可被表示，大于C的数可被表示。
 证明：
@@ 行 25: / 行 25: @@
 其中t为整数。取适当的t，使得y位于0到a-1之间。这只需在y0上加上或减去若干个a，即可得到这样的t。
-第一步：证明大于A的数都可以被表示。当n大于A时：
+第一步：证明大于C的数都可以被表示。当n大于C时：
-$$ax=c-by>ab-a-b-by\geqslant ab-a-b-b(a-1)=-a$$
+$$ax=n-by>ab-a-b-by\geqslant ab-a-b-b(a-1)=-a$$
 于是x也是非负整数。
-第二步：证明A不可被表示，进而n与A-n不可能都被表示。
+第二步：证明C不可被表示，进而n与C-n不可能都被表示。
 反证法。若ax+by=ab-a-b有非负整数解x、y，则：
@@ 行 43: / 行 43: @@
 矛盾！第二步证完。
-第三步：证明如果n不可被表示，则A-n可被表示。
+第三步：证明如果n不可被表示，则C-n可被表示。
 由上可知，若n不可被表示，由于上述方程中已规定y在0到a-1之间，则x为负。所以：
@@ 行 49: / 行 49: @@
 $$ab-a-b-ax-by=a(-x-1)+b(a-1-y)$$
-显然-x-1和a-1-y均非负，于是A-n可被表示。
+显然-x-1和a-1-y均非负，于是C-n可被表示。
-=====小于等于K 的能被表示的非负整数的数量=====
+=====几何意义=====
-考虑mod B 意义下每个剩余系（ 0 · · ·B − 1 ）的最小能被表示的值是多少——大于他们的可以通过+kB 得到。
+重新观察方程ax+by=n，将它看成一条直线。直线与两坐标轴在第一象限围成三角形。
-观察原方程，A的若干倍数0, A, · · · , (B − 1)A 在mod B 意义下互不相同。这些数恰好是这些最小值。那么当K < AB 时，小于等于K 的能被表示的非负整数的数量是：
+当n小于ab的时候，这个直线在第一象限，至多只能通过一个整点。
-$$ Σ_{i=0}^{⌊\frac{K}{A}⌋}⌊\frac{K − iA}{B}⌋$$
+根据上述讨论：当n可以被表示的时候，直线恰好经过一个整点；当n不可以被表示的时候，直线不经过整点（在第一象限）。
-这是一个非常经典的直线下整点问题，使用类欧几里得算法可以在O(log max(A,B)) 的时间内求解。因此我们得到了计算小于等于K 的能被表示的非负整数的数量的工具。
+这结论也可以理解为：作三角形(0,0)(b,0)(0,a)。随着n从0不断增加，直线向右上方平移，整点会一个一个地通过直线，直到最后才撞上两个整点。
-<del>但是直线下整点（类欧几里得）不会。只能等待大佬完善了。</del>
+因此，小于等于n的能被表示的非负整数的数量，恰好就是直线ax+by=n（含）与两坐标轴（含）在第一象限围成三角形覆盖的整点个数。
+（另一种解释）
+考虑模b意义下每个剩余系中最小能被表示的值是多少——大于他们的可以通过增加若干个b得到。
+观察原方程，a的若干倍数0, a, · · · , (b − 1)a 在mod b 意义下互不相同。这些数恰好是这些最小值。那么当n<ab时，小于等于n的能被表示的非负整数的数量是：
+$$ \sum\limits_{i=0}^{\left[\frac{n}{a}\right]}\left[\frac{n − ia}{b}\right]$$
+这是一个非常经典的直线下整点问题，恰好是这条直线：
+$$y=-\frac{a}{b}x+\frac{n}{b}$$
+即ax+by=n。
+（解释完）
+使用类欧几里得算法可以在O(log max(a,b)) 的时间内求解。因此我们得到了计算小于等于n的能被表示的非负整数的数量的工具。
+<del>但是直线下整点（类欧几里得）不会。只能等待大佬来完善了。</del>
 以下是例题。

CVBB ACM Team

用户工具

站点工具

差别

页面工具