欧几里得定理与拓展

又称辗转相除法，求两个数的最大公因数

• 更相减损术

• 辗转相除法

• 贝祖定理

• 拓展欧几里得算法

更相减损术

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数
复杂度会退化为O(n)

  #include<iostream>
  #include<cmath>
  using namespace std;
  int gcd(int x,int y){
      if(x==y) return y;
      if(x<y) swap(x,y);
      gcd(y,x-y);
  }
  int main()
  {
      int a,b;
      cin>>a>>b;
      cout<<gcd(a,b)<<endl;
      return 0;
  } 

证明：
若所求a,b的最大公约数为m，a>b，$a=k1\times m,b=k2\times m$,k1,k2互质
则$a-b=k1\times m-k2\times m=(k1-k2)\times m$
可知k2与(k1-k2)互质
反证上述结论：
存在两个互质的数a,b,使得b与a-b不互质
令，b与a-b,分解质因数,存在最大公因数k1
$b=k1\times c1,a-b=k1\times c2$
则 $a-b=a-k1\times c1=k1\times c2$
则$a=k1\times (c1+c2)$，此时a,b不互质，矛盾，得证
所以(k1-k2)不断接近并最后等于1，相等时即为答案

辗转相除法

是更相减损术的加速版，复杂度稳定(logn)
将更相减损术的多次(k1-k2)操作更改为取mod

#include<iostream>
#include<cmath>
using namespace std;
int gcd(int x,int y){
    if(y==0) return x;
    return gcd(y,x%y);
}
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<gcd(a,b);
    return 0;
} 

贝祖定理

也称裴蜀定理，描述了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性不定方程（称为裴蜀等式）
a,b是不全为0的整数，则存在整数x,y,使得
$a\times x+b\times y=gcd(a,b)$
证明：
由欧几里得算法可知：
设d=gcd(a,b)，$a>b,a=k_1,b=k_2$
$k_1=q_1\times k_2+k_3$
$k_2=q_2\times k_3+k_4$
$k_3=q_3\times k_4+k_5$
......
$k_{n-2}=q_{n-2}\times k_{n-1}+k_n$
$k_{n-1}=q_{n-1}\times k_n$
$k_1,k_2,k_3,k_4......k_n$之间两两之间存在且仅存在最大公因数$k_n$
所以 $k_n=k_{n-2}-q_{n-2}\times k_{n-1}$
$\qquad k_n=k_{n-2}-q_{n-2}\times (k_{n-3}-q_{n-3}\times k_{n-2})$
......
可知无限的递归可以到底层的$k_1,k_2$
所以一定存在有整数使得等式成立

拓展欧几里得定理

在已知gcd(a,b)时，求解满足$a\times x+b\times y=gcd(a,b)$的一组x,y
解：
由贝祖定可知，此解一定存在
$a\times x_1+b\times y_1=gcd(a,b)$
$b\times x_2+a\%b\times y_2=gcd(a,b)$
......
一直递归至底层为
$a'\times x_n+b'\times y_n=gcd(a,b)$
此时$a'=gcd(a,b)$，$b'=0$,$x_n=1,y_n=0$
之后回溯：
联立$a\times x_1+b\times y_1=gcd(a,b)$与$b\times x_2+a\%b\times y_2=gcd(a,b)$
$a\times x_1+b\times y_1=b\times x_2+a\%b\times y_2$
$a\times x_1+b\times y_1=b\times x_2+(a-a/b\times b)\times y_2$
$a\times x_1+b\times y_1=a\times y_2+b\times (x_2-a/b\times y_2)$
所以$x_1=y_2,y_1=(x_2-a/b\times y_2)$
有此可以递归求出次方程的一组解

void ex_gcd(ll a,ll b,ll &x,ll &y){
  if(b==0){
      x=1,y=0;
      return ;
  }
  ex_gcd(b,a%b,x,y);
  int kk=x;
  x=y;
  y=kk-a/b*y;
  return;
}

【模板】二元一次不定方程(exgcd)
判断无解:
贝祖定理可知，当且仅当$c|(a,b)$时有正整数解
我们用拓展欧几里得算得方程：
$\qquad a'\times x_0+b'\times y_0=gcd(a,b)$
的一组特解
可知原方程的一组特解为：
$x=x'\times (c/d),y=y'\times (c/d)$
首先，我们将x，y同步放大或者缩小至x的最小正整数解

ll k=0;
if(x>=0){
	k=(x-1)/(b/d);
	x-=k*(b/d);
	y+=k*(a/d);
}
if(x<0){
	k=-x/(b/d)+1;
	x+=k*(b/d);
	y-=k*(a/d);
}

可知若此时的y<=0则没有正整数解
根据不定方程的相关内容可知，由特解可以知晓其整个解系

if(y>0){
	printf("%lld ",(y-1)/(a/d)+1);
	printf("%lld ",x);
	printf("%lld ",(y-1)%(a/d)+1);
	printf("%lld ",x+(y-1)/(a/d)*(b/d));
	printf("%lld\n",y);
}else{
	printf("%lld ",x);
	printf("%lld\n",y+((-y)/(a/d)+1)*(a/d));
}

ps:
注意分析最大最小x,y值的求法

#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long 
using namespace std;
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		x=1;y=0;
		return a;
	}
	ll ans=exgcd(b,a%b,x,y);
	ll kk=x;
	x=y;
	y=kk-a/b*y;
	return ans;
}
int main()
{
	int t;
	cin>>t;
	while(t){
		ll a,b,c;
		scanf("%lld%lld%lld",&a,&b,&c);
		ll x,y;
		ll d=exgcd(a,b,x,y);
		if(c%d!=0){
			printf("-1\n");
			t--;
			continue;
		}
		x=(x*c/d);
		y=(y*c/d);
		ll k=0;
		if(x>=0){
			k=(x-1)/(b/d);
			x-=k*(b/d);
			y+=k*(a/d);
		}
		if(x<0){
			k=-x/(b/d)+1;
			x+=k*(b/d);
			y-=k*(a/d);
		}
		if(y>0){
			printf("%lld ",(y-1)/(a/d)+1);
			printf("%lld ",x);
			printf("%lld ",(y-1)%(a/d)+1);
			printf("%lld ",x+(y-1)/(a/d)*(b/d));
			printf("%lld\n",y);
		}else{
			printf("%lld ",x);
			printf("%lld\n",y+((-y)/(a/d)+1)*(a/d));
		}
		t--;
	}
	return 0;
}