# 歐幾里得算法,擴展歐幾裡得算法

###### tags: `Algorithm`

## 歐幾裡得算法
### gcd(a,b)=gcd(b,r)

> 已知 a\b=q...r
> a=bq+r

d=a,b 的公因數
→ d 為 a-bq的因數
→ d 為 r 的因數
→ a,b 的公因數為r的因數
:::info
gcd(a,b)=gcd(b,r)
:::

### 輾轉相除法

> (703,407)

703 / 407 = 1 ... 296

→ 求 (407,296)

> (407,296)

407 / 296 = 1...111

> 求 (206,111)
.
.
.

## 擴展歐幾裡得算法
>a,b ∈ Z
必存在整數 x,y 使ax+by = gcd(a,b)
求x,y

設 a*x1 + b*y1 = gcd(a, b) (1)

   b*x2 + a%b * y2 = gcd(b, a%b)(2)

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

所以有a*x1 + b*y1 = b*x2 + (a - a/b * b)*y2  (此處的'/'為向下取整除)

化簡有a*x1 + b*y1 = a*y2 + b* (x2 – a/b * y2)
x1 = y2, y1 = (x2 - a/b * y2)

:::info
結論:
x1 = y2, y1 = (x2 - a/b * y2)
:::

void exGcd (int a, int b, int &x, int &y)
{
    int t;
    if (b==0) x = 1, y = 0;
    else      gcd(b,a%b,x,y), x = y, y = t-a/b*y;
}