\(Q\):什么是\(GCD\)?
- \(GCD\)
\(GCD\)，即最大公约数（\(Greatest\ Common\ Divisor\)）
对于两个自然数\(a,b\)，定义\(GCD(a,b)\)为\(a,b\)所有公共约数中最大的一个，即\(GCD(a,b)=\max\{x\in N^*,x|a\)且\(x|b\}\)
然后是关于\(GCD\)的算法即其扩展
\(Part1\) 欧几里得算法
\(Q\):这个算法有什么用？
此算法可以在\(log\)级别里求出两个数\(a,b\)的\(GCD\)
- 欧几里得算法
对于\(a,b\)，设它们的\(GCD\)为\(d\)。
则有：\(d|a\)且\(d|b\)
设\(a=k*{}b+r(k=\left\lfloor\frac{a}{b}\right\rfloor,r=a\mod b)\)
则：\(d|(a-k*{}b)\)，即\(d|r\)
所以\(GCD(a,b)=GCD(b,r)=GCD(b,a\mod b)\)
最后递归求解，可在\(O(log_2a)\)内得解。
时间复杂度 \(O(log_2a)\)
空间复杂度 \(O(log_2a)\)(递归栈)
实际复杂度一般到不了此上界。
代码：
//求GCD(a,b)#includeint GCD(int a,int b){ return b?GCD(b,a%b):a; //当b为0时，GCD(a,0)=a，充当递归边界。}int main(){ int a,b; scanf("%d%d",&a,&b); printf("%d\n",GCD(a,b)); return 0;}
\(Part2\) 扩展欧几里得
\(Q\):这个奇怪的算法又是什么啊？
首先，先来看一个不定方程：
\[ax+by=c\]
扩展欧几里得就是用来求此方程的不定解\((x,y)\)的。
准备知识：
- \(Bezout\)定理
对于两个整数\(a,b\)存在一对整数\(x,y\)，满足\(ax+by=GCD(a,b)\)
证明：
在调用欧几里得算法时，当\(b=0\)，显然有\(x=1,y=0\)满足定理。
当\(b\not= 0\)时，若已经求得，\(x,y\)，使得
\[bx+(a\mod b)y=GCD(b,a\mod b)\]
则
\[bx+(a-b\left\lfloor\frac{a}{b}\right\rfloor)y=GCD(b,a\mod b)\]
\[ay+b(x-\left\lfloor\frac{a}{b}\right\rfloor y)=GCD(b,a\mod b)\]
设\(x'=y,y'=x-\left\lfloor\frac{a}{b}\right\rfloor y\)，则有
\[ax'+by'=GCD(b,a\mod b)=GCD(a,b)\]
利用数学归纳法，知道\(Bezout\)成立。
同时，我们可以利用此定理求出一组\(ax+by=GCD(a,b)\)的解。
时间复杂度 \(O(log_2a)\)
空间复杂度 \(O(log_2a)\)
代码：
//求x,y使得ax+by=GCD(a,b)，同时得到GCD(a,b)#includeint ExGCD(int a,int b,int &x,int &y){ if(!b){x=1,y=0;return a;}//递归边界 int GCD=ExGCD(b,a%b,x,y); int Tmp=x; x=y,y=Tmp-a/b*y; return GCD;}int main(){ int a,b,GCD,x,y; scanf("%d%d",&a,&b); GCD=ExGCD(a,b,x,y); printf("%d %d %d\n",GCD,x,y); return 0;}
接着回到正题：对于方程\(ax+by=c\)，它有解仅当\(GCD(a,b)|c\)。
证明？不会，记住就行，毕竟显然。
接着，求出方程\(ax+by=GCD(a,b)\)的一组解，则：
\[ax+by=GCD(a,b)\]
\[\frac{c}{GCD(a,b)}*{}(ax+by)=c\]
\[a*\frac{cx}{GCD(a,b)}+b*\frac{cy}{GCD(a,b)}=c\]
于是就有了一组解：\(x'=\frac{cx}{GCD(a,b)},y'=\frac{cy}{GCD(a,b)}\)(对\(x,y\)同时乘上\(\frac{c}{GCD(a,b)}\))
于是问题得解。
时间复杂度 \(O(log_2a)\)
空间复杂度 \(O(log_2a)\)
代码：
//求x,y使得ax+by=c，同时得到GCD(a,b)#includeint ExGCD(int a,int b,int &x,int &y){ if(!b){x=1,y=0;return a;}//递归边界 int GCD=ExGCD(b,a%b,x,y); int Tmp=x; x=y; y=Tmp-a/b*y; return GCD;}int main(){ int a,b,c,GCD,x,y; scanf("%d%d%d",&a,&b,&c); GCD=ExGCD(a,b,x,y); if(c%GCD)return puts("Orz I cannot find it!"),0;//无解 int d=c/GCD; printf("%d %d %d\n",GCD,x*d,y*d); return 0;}
关于通解以及\(x\)最小正整数解。
设\(d=GCD(a,b)\)，
\(x_0,y_0\)为\(ax+by=GCD(a,b)\)的一组特解，
\(x=x_0+km,y=y_0+kn(k\in \mathbb{Z})\)为方程的通解表示（k为任意整数），
则：
\[ax+by=ax_0+by_0\]
\[a(x_0+km)+b(y_0+kn)=ax_0+by_0\]
\[am+bn=0\]
显然，当\(m=-b,n=a\)时等式成立。
又因为要把\(m,n\)比例降到最小，所以同时除去\(GCD\)。
最后的通解表示为：
\[x=x_0-k\frac{b}{d},y=y_0+k\frac{a}{d}(k\in \mathbb{Z})\]
同理，对于方程\(ax+by=c\)的通解为：
\[x=\frac{c}{d}x_0-k\frac{b}{d},y=\frac{c}{d}y_0+k\frac{a}{d}(k\in \mathbb{Z})\]
所以求\(x\)的最小整数解只需要将\(x\mod \frac{b}{d}\)再推出\(y\)即可。
时间复杂度 \(O(log_2a)\)
空间复杂度 \(O(log_2a)\)
代码：
//求ax+by=c的x最小正整数解。#includeint ExGCD(int a,int b,int &x,int &y){ if(!b){x=1,y=0;return a;}//递归边界 int GCD=ExGCD(b,a%b,x,y); int Tmp=x; x=y; y=Tmp-a/b*y; return GCD;}int main(){ int a,b,c,d,x,y; scanf("%d%d%d",&a,&b,&c); d=ExGCD(a,b,x,y); if(c%d)return puts("Orz I cannot find it!"),0;//无解 x*=c/d,y*=c/d; int f=b/d; x=(x%f+f)%f; y=(c-a*x)/b; printf("%d %d\n",x,y);//x最小正整数解。 return 0;}
所有性质证明到此结束。
欧几里得是个好东西，然而我不会用。
数论博大精深，不能就此止步，还要继续探索。
祝自己\(++OI::RP\)