标签：right end gcd 数论 dfrac Note ax cases 同余

1. 扩展欧几里得算法

1.1. 介绍

扩展欧几里得算法用于求 \(ax+by=\gcd(a,b)\) 的一组特解（整数解）。
推导如下：
设 \(\begin{cases}ax_1+by_1=\gcd(a,b)\\bx_2+(a\mod b)y_2=\gcd(b,a\mod b)\end{cases}\)
由欧几里得算法可知 \(\gcd(a,b)=\gcd(b,a\mod b)\)。
联立有：

\[ax_1+by_1=bx_2+(a\mod b)y_2 \]

\[ax_1+by_1=bx_2+(a-\left\lfloor\dfrac{a}{b}\right\rfloor\times b)y_2 \]

\[ax_1+by_1=ay_2+b(x_2-\left\lfloor\dfrac{a}{b}\right\rfloor\times y_2) \]

可得：

\[\begin{cases}x_1=y_2\\y_1=x_2-\left\lfloor\dfrac{a}{b}\right\rfloor\times y_2\end{cases} \]

最后在求 \(\gcd\) 的过程中求解 \(x,y\) 即可。

1.2. 常见技巧

二元一次不定方程通解

对于 \(ax+by=c\) 这种一元二次不定方程，由裴蜀定理可知，当 \(\gcd(a,b)\nmid c\) 时，此方程无整数解。
当有整数解时，我们将其转化为 \(ax+by=\gcd(a,b)\) 的形式，然后用扩展欧几里得算法求解。
我们设扩展欧几里得算法求出的解为 \(X,Y\)，\(ax+by=c\) 方程所求的一组特解为 \(x',y'\)，有：

\[\begin{cases}x'=\dfrac{Xc}{\gcd(a,b)}\\y'=\dfrac{Yc}{\gcd(a,b)}\end{cases} \]

因为 \(ax'\) 与 \(by'\) 的和恒为 \(c\)，有：

\[a(x'+db)+b(y'-da)=c \]

其中，我们要保证 \(x'+db,y'-da\) 均为整数，取得最小变化量：

\[\begin{cases}d_x=\dfrac{b}{\gcd(a,b)}\\d_y=\dfrac{a}{\gcd(a,b)}\end{cases} \]

最后得出通解形式：

\[\begin{cases}x=x'+sd_x\\y=y'+sd_y\end{cases} \]

接下来是关于正整数解的内容。
限制 \(x,y>0\)，解得：

\[\left\lfloor\dfrac{-x'+1}{d_x}\right\rfloor\le s\le\left\lceil\dfrac{y'-1}{d_y}\right\rceil \]

至此，我们可以判断正整数解个数。当 \(s\) 取极值时，我们也可求出 \(x,y\) 的极值。

标签：right,end,gcd,数论,dfrac,Note,ax,cases,同余
From： https://www.cnblogs.com/Eon-Sky/p/17627773.html