# 拓展欧几里得

## 拓展欧几里得

$gcd(a,b)=gcd(b,a%b)$

 1  ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} 

### ax+by=gcd（a,b)

$x_2,y_2$满足$bx_2+(a;mod;b)y_2=gcd(b,a;mod;b)$

$gcd(a,b)x+0\times y=gcd(gcd(a,b),0)$

  1 2 3 4 5 6 7 8 9 10 11 12 13  ll exgcd(ll a, ll b, ll &x, ll &y) { if (!b) { x = 1; y = 0; return a; } ll d = exgcd(b, a % b, x, y); ll t = x; x = y; y = t - (a / b) * y; return d; } //exgcd返回的值为gcd（a，b） 

### ax+by=c

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25  ll exgcd(ll a, ll b, ll &x, ll &y) { if (!b) { x = 1; y = 0; return a; } ll d = exgcd(b, a % b, x, y); ll t = x; x = y; y = t - (a / b) * y; return d; } //ax+by=c,ax%b=c%b; ll lieu(ll a,ll b,ll c,ll &x,ll &y) { ll d=exgcd(a,b,x,y); if(c%d!=0)return 0; ll k=c/d; x*=k; y*=k; ll t=b/d; x=(x%t+t)%t; y=(c-a*x)/b; return x; } 

### 线性同余方程

$ax\equiv c(mod;b)$