No.1 前置知识
-
欧几里得算法（辗转相除法）
-
裴蜀定理
No.2 算法，证明及函数
扩展欧几里得算法用来解决这样一个问题：给定两个非零的整数 \(a\) 和 \(b\)，求一组整数解 \((x，y)\) 使得 \(ax+by = gcd(a,b)\) 成立（通过裴蜀定理可知一定存在解）。
证明：
设 \(ax_1+by_1=gcd(a,b)\)，设 \(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-kb(k\) 为商且 \(k \in \mathbb Z)\)
又\(∵k=\lfloor \displaystyle \frac{a}{b} \rfloor\)
\(∴ax_1+by_1=bx_2+(a-b\lfloor \displaystyle \frac{a}{b} \rfloor)y_2\)
整理得：\(ax_1+by_1=ay_2+b(x_2-\lfloor \displaystyle \frac{a}{b} \rfloor y_2)\)
\(∴ \exists x_1=y_2,y_1=x_2-\lfloor \displaystyle \frac{a}{b} \rfloor y_2\)
可以看出：\((x_1,y_1)\) 这组解由 \((x_2,y_2)\) 得来
不难发现：当\(x_n,y_n\) 关于 \(gcd(a,0)\) 时，\(ax_n+by_n=a,\exists x_n=1,y_n=0\)
\(\exists\) 这组边界整数解可得 \(x_1,y_1\)
函数:
void exgcd(int a,int b){
if(b==0){
x=1;
y=0;
return;
}
exgcd(b,a%b);
int t=x;
x=y;
y=t-(a/b)*y;
}