gcd与exgcd(裴蜀定理)

gcd（欧几里得算法）与最大公因数

1. 公式：$gcd(a,b)=gcd(b,a$%b$)$

2. 证明：
   设$a>b$，证明$a,b$的公因数和$b,a-b$的公因数是同样的一堆数
   首先，有结论:若 $x|a,x|b,那么x|(a-b)$.
   设$a$和$b$的公因子集合为$S1$，$b$ 和$(a–b)$的公因子集合为$S2$。那么，
   对于任意的 $x\in S1$，有$x|a$，且$x|b$，所以 $x|(a–b)$，则 $x$ $\in$ S2$，于是$S1$ $\subset$ $S2$；
   对于任意的 $x\in S2$，有 $x|b$，且 $x|(a–b)$，所以 $x|a$，则 $x\in S1$，于是 $S2$ $\subset$ $S1$。
   所以 $S1=S2$，$gcd(a,b)=max(S1)=max(S2)=gcd(b,a–b)$。
   证明了 $gcd(a,b)=gcd(b,a–b)$，也就可以进一步证明 $gcd(a,b)=gcd(b,amodb)$。

3. 代码：

#define ll long long
ll gcd(ll a,ll b)
{
	if(b==0)return a;
	else rteutn gcd(b,a%b);
}

4. 复杂度：$O(lo{g}_{2}max(a,b))$

exgcd(扩展欧几里得算法)

1. 前置知识：裴蜀定理$qwq$
   （1） 对任何$a,b\in Z$和它们的最大公约数$d$，关于未知数$x$和$y$的线性不定方程（称为裴蜀等式）：$ax+by=c$有整数解$(x,y)$当且仅当$d\mid c$，可知有无穷多解。特别地，一定存在整数$x$,$y$，使$ax+by=d$成立。
   ( 2 )推论：
   $a$,$b$互质的充要条件是存在整数$x$,$y$使$ax+by=1$
   ( 3 )证明：
   $A:$对于$(a,b\in Z)$，$ax+by=gcd(a,b)$一定有整数解$x,y$
   设$d=gcd(a,b)$,可得$d|a,d|b,d|(ax+by)$
   满足对于某个 $x,y$ $\in$ $Z$,有$n=ax+by$的$n$的集合叫$a$与$b$的线性组合集，设$s$是$a$与$b$的线性组合集中最小的元素。
   设$q=$ $\lfloor$ $\frac{a}{s}$ $\rfloor$ 则有$r=$ $a$ $mod$ $s$ $=a-qs=a-q(ax+by)=a(1-qx)+b(-qy)$所以$r$也是$a$与$b$的线性组合集中的元素。已知$s$是这个线性组合集中的最小正整数，$0$$\le$ $r$ $\le$ $s$,所以$r=0$。所以$s|a$。同理$s|b$。所以$s$是$a与b$的公因数。
   因为$d$是最大公约数，所以$d$ $\le$ $s$。
   因为对于任意$x,y\in Z$，有$d\mid (ax+by)$，而对于某个$x,y\in Z$，有$s=ax+by$，所以有$d\mid s$,故 $d$ $\ge$ $s$。
   显然，$s=d$ 所以$s=gcd(a,b)$
   根据$s$的定义，$s$是$a$与$b$的线性组合集中的最小正元素，故$ax+by=gcd(a,b)$一定有整数解$x,y$，亦可知对于$a,b\in Z$，$gcd(a,b)$是$ax+by(x,y\in Z)$的最小正元素
   $B:$对于$(a,b\in Z)，ax+by=c$有整数解的条件是$gcd(a,b)\mid c$
   充分性：设$d=gcd(a,b)$，已知$ax+by=d$一定有整数解，设其解为$(x0,y0)$。$d\mid c$，则存在$k\in Z$，使得$c=kd=k(ax+by)=a(kx)+b(ky)$，即解为$(kx0,ky0)$。
   必要性：因$ax1+by1=c，x1,y1\in Z$，设$d=gcd(a,b)$，有$d\mid a$，$d\mid b$，$d\mid (ax1,by1)$，即$d\mid c$
   是不是简单易懂！！！
   是不是简单易懂！！！
   是不是简单易懂！！！

2. exgcd
   exgcd可以用来判断并求解形如$ax+by=c$ 的方程，当且仅当$gcd(a,b)|c$时，存在整数解$x,y$(证明：裴蜀定理)。
   于是它也可以用来求逆元（链接在下面噻qwq）

3. 怎么求解？
   $ax+by=gcd(a,b)$可以化成$ay+b(x-$ $\lfloor$ $\frac{a}{b}$ $\rfloor$$)x=gcd(a,b)$然后可以在gcd的循环过程中完成计算
   可以背代码，但是如果理解的话，就可以当场现推了！！！
   个人认为，还是重在理解，背代码没有灵魂

4. 怎么现推呢$qwq$
   $gcd(a,b)=gcd(b,a$ $mod$ $b)$，在gcd递归中我们会使$a=b,b=a$ $mod$ $b$.
   则有方程$b\ast x_1+(a$ $mod$ $b)\ast y_1=gcd(b,a$ $mod$ $b)=gcd(a,b)$
   把 $a$ $mod$ $b$拆开写
   可以得到$b\ast x_1+(a-b\ast \lfloor a/b\rfloor )\ast y_1=gcd(a,b)$
   前置知识乘法分配律hhhh
   即：$a\ast y_1+b\ast (x_1-\lfloor a/b\rfloor \ast y_1)=gcd(a,b)$
   所以原方程中：$x=y_1,y=x_1-\lfloor a/b\rfloor \ast y_1$。

5. 代码

ll exgcd(ll &x,ll &y,ll a,ll b)
{
	if(b==0)
	{
		x=1;y=0;return a;
	}
	else
	{
		return exgcd(x,y,b,a%b);
	}
	ll t=y;y=x-(a/b)*y;x=t;
}

这段代码的返回值为$gcd(a,b)$。$x,y$是方程$ax+by=gcd(a,b)$的一组解。
那么对于方程$ax+by=c(gcd(a,b)|c)$的一组解是$x^{\prime }=x\ast c/gcd(a,b)，y^{\prime }=y\ast c/gcd(a,b)$
6. 求多组解
$ax+by=c$
$a{x}_1+b{y}_1=c$
可得$a(x-x_0)+b(y-y_0)=0$
两边同时除以gcd（a,b）得$\frac{a(x-x_0)}{gcd(a,b)}+\frac{b(y-y_0)}{gcd(a,b)}=0$
因为$\frac{a}{gcd(a,b)}$与$\frac{b}{gcd(a,b)}$互质
所以$(x-x_0)是gcd(a,b)$的倍数
所以$(x-x_0)=tgcd(a,b)$
$x=t（gcd(a,b)）+x_0$


em。。。exgcd的性质使它可以被用来求逆元
关于逆元。。。
链接在这里啦关于逆元