凌：前言
\(\tt \# include~"\)\(\tt{\small\texttt{扩展欧几里得算法 - }}OI~Wiki\)\(\tt "\)
\(\tt \# include~"\)\(\tt{\small\texttt{关于}}~exgcd~{\small\texttt{求得特解的数值范围 - }}ycx's~blog\)\(\tt "\)
\({\tt \# define}~~a/b~~\left\lfloor\dfrac ab\right\rfloor\)
\({\tt \# define}~~d~~\gcd(a,b)\)
\({\tt \# define}~~a'~~a/d\)
\({\tt \# define}~~b'~~b/d\)
依：扩展欧几里得算法
\(a,b\) 为非负整数，且不同时为 \(0\) ，解关于 \(x,y\) 的不定方程 \(ax+by=d\) 。
使用辗转相除法求解。
假设我们已知
\[bx+(a\bmod b)y=\gcd(b,a\bmod b) \]的一组解为 \(x_1,y_1\) ，那么
\[bx_1+(a\bmod b)y_1=d \]\[bx_1+(a-(a/b)\times b)y_1=d \]\[ay_1+b(x_1-(a/b)\times y_1)=d \]所以 \(\begin{cases}x_0=y_1\\y_0=x_1-(a/b)\times y_1\end{cases}\) 是 \(ax+by=d\) 的一组解。
边界条件为 \(b=0\) ，此时方程为 \(ax=a\) ，取 \(x=1,y=0\) 即可。
int exgcd(int a,int b,int &x,int &y) {
if (!b) { x=1,y=0; return a; }
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
exgcd 得出的 \(x_0,y_0\) 是原方程的一组特解。而通解形式为
\[\begin{cases}x=x_0+b'k\\y=y_0-a'k\end{cases}~(k\in\bf Z) \]证明略。
二：值域分析
\(x_0,y_0\) 一定是所有解中 \(|x|+|y|\) 最小的（之一）。并且：
-
若 \(a=0\) ，则 \(x_0=0,y_0=1\) ；
-
若 \(b=0\) ，则 \(x_0=1,y_0=0\) ；
-
若 \(ab\ne 0,a=b\) ，则 \(x_0=0,y_0=1\) ；
-
若 \(ab\ne 0,a\ne b\) ，则 \(|x_0|\le \dfrac b2,|y_0|\le \dfrac a2\) 。
第 1~3 条没啥好说的。下面给出第 4 条的证明。
不难发现 \(\tt exgcd(a,b,x,y)\) 和 \(\tt exgcd(a',b',x,y)\) 得到的解是相同的。
所以不妨设 \(a,b\) 互质，原命题不会变弱。
考虑归纳。
设 exgcd 求解 \(bx+(a\bmod b)y=1\) 得到的是 \(x_1,y_1\) 。
若 \(b=1\) ，则 \(x_1=1,y_1=0\)（第 2 条）。
计算得 \(x_0=0,y_0=1\) ，显然满足第 4 条。
若 \(b\ne 1\) ，易证 \(b(a\bmod b)\ne 0\) 且 \(b\ne a\bmod b\) ，符合第 4 条的前提条件。
只需证明：由 \(|x_1|\le \dfrac{a\bmod b}2,|y_1|\le\dfrac b2\) 可以推出 \(|x_0|\le \dfrac b2,|y_0|\le \dfrac a2\) 。
这样就完成了一个完整的归纳证明。
最后，我们有
\[\begin{aligned} |x_0|&=|y_1|\\ &\le \dfrac b2\\ |y_0|&=|x_1-(a/b)\times y_1|\\ &\le |x_1|+|(a/b)\times y_1|\\ &\le \dfrac{a\bmod b}2+(a/b)\times\dfrac b2\\ &=\dfrac{(a\bmod b)+(a/b)\times b}2\\ &=\dfrac a2 \end{aligned}\]证毕！
\(x_0,y_0\) 一定是所有解中 \(|x|+|y|\) 最小的一组（之一）。
至于最开始的这句话，其实已经是显然的了，考虑通解形式即可证明，不再赘述。
标签：le,bmod,dfrac,欧几里得,exgcd,times,算法,tt From： https://www.cnblogs.com/REKonib/p/17065157.html