裴蜀定理
exgcd
之前写得不好所以重写一遍
exgcd 即扩展欧几里得算法，常用来求 \(ax + by = \gcd{(a,b)}\) 的一组解。
设一组解为 \(x_1,y_1\)，即 \(ax_1 + by_1 = \gcd{(a,b)}\)，我们取 \(x_2,y_2\) 满足 \(bx_2 + (a\bmod b)y_2 = \gcd{(b,a\bmod b)}\)。
显然 \(\gcd{(a,b)} = \gcd{(b,a\bmod b)}\)，所以 \(ax_1 + by_1 = bx_2 + (a\bmod b)y_2\)。
由 \(a\bmod b = a - b\left\lfloor\dfrac{a}{b}\right\rfloor\)，展开得 \(ax_1 + by_1 = bx_2 + (a - b\left\lfloor\dfrac{a}{b}\right\rfloor)y_2\)
化简得 \(ax_1 + by_1 = ax_2 + b(x_2 - \left\lfloor\dfrac{a}{b}\right\rfloor)\)，故 \(x_1 = y_2 , y_1 = x_2 - \left\lfloor\dfrac{a}{b}\right\rfloor\)。
故我们求解的 \(x_1,y_1\) 即 \(x_2,y_2\)，考虑其满足的条件与原方程相同，所以可以迭代求解 \(x_2 = x_3,y_2 = y_3\)……
标签：lfloor,right,gcd,dfrac,bmod,exgcd,ax,取余,裴蜀 From： https://www.cnblogs.com/qzhwlzy/p/16878553.html