欧几里得与扩展欧几里得定理

$$ \gcd(a,b) = \gcd (b,a \text{ mod } b) $$

$$ \begin{cases} ax_1 + by_1 = \gcd(a,b) \newline bx_2 + (a\text{ mod }b)y_2 = \gcd(b,a\text{ mod }b) \end{cases} \Rightarrow \begin{cases} x_1 = y_2 \newline y_1 = x_2- \lfloor\dfrac{a}{b}\rfloor \times y_2 \end{cases}$$

一 欧几里得定理

1 最大公约数

最大公约数（Greatest Common Divisor，GCD），是指对于两个整数$a,b$，找到一个最大的整数$k$，使得$k|a$且$k|b$（“$|$”表示整除）。

2 欧几里得定理

对于任意整数对$(a,b)$，它们的最大公约数都等于整数对$(b,a\text{ mod }b)$的最大公约数。用公式表达就是这样：
$$\forall a,b\in Z , \gcd(a,b) = \gcd(b, a\text{ mod }b)$$

证明请参照OI Wiki - gcd。

3 代码实现

当$b=0$时，可知$\gcd(a,b) = \gcd(a,0) = a$。故递推$\gcd(a,b) = \gcd(b,a\text{ mod }b)$直到$b=0$。

实现如下：

int gcd(int a,int b){
    if(!b) return a;
    return gcd(b, a%b);
}

甚至可以压行：

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

---

二 扩展欧几里得定理

1 模型

扩展欧几里得定理（EX-GCD）用于求解关于$x,y$的，形如$ax+by = \gcd(a,b)$方程的一组可行解。
该定理的基本内容如下：

设$ax_1 + bx_2 = \gcd(a,b)$，$bx_2 + (a\text{ mod }b)y_2 = \gcd(b,a\text{ mod }b)$，则有$x_1= y_2, y_1 = x_2- \lfloor\dfrac{a}{b}\rfloor \times y_2$。即为引言中的公式：

$$ \begin{cases} ax_1 + by_1 = \gcd(a,b) \newline bx_2 + (a\text{ mod }b)y_2 = \gcd(b,a\text{ mod }b) \end{cases} \Rightarrow \begin{cases} x_1 = y_2 \newline y_1 = x_2- \lfloor\dfrac{a}{b}\rfloor \times y_2 \end{cases}$$

证明也请参见OI Wiki - exgcd。

2 代码实现

当$b=0$时，$\gcd(a,b) = \gcd(a,0) = a$。此时$ax + by = \gcd(a,b) = a$的一组可行解是$\begin{cases} x = 1 \ y = 0 \end{cases}$。把这个作为边界条件带入gcd函数，不断向上面一样递推至$b=0$，再在回溯过程中计算答案即可。

void exgcd(int a,int b,int &x,int &y){
    if(!b){
        x = 1;
        y = 0;
        return;
    }
    exgcd(b,a%b,x,y);
    int t = x;     //保存x2 
    x = y;         //计算x1 
    y = t-(a/b)*y; //计算y1 
}

3 解的关系

设$k$为任意整数，则当$x_1,y_1$是方程$ax+by = \gcd(a,b)$的一组解时，$x_1+kb,y_1-ka$也是该方程的一组解。

证明如下：
因$ax_1 + by_1= \gcd(a,b)$①，得$ax_1 + by_1 + k·a·b - k·a·b= \gcd(a,b)$。
变换得$ax_1 + a·kb + by_1 - b·ka = \gcd(a,b) , a(x_1 + kb) + b(y_1 - ka) = \gcd(a,b)$②。
因①式成立，故 ② 式成立。即$x_1+kb,y_1-ka$是方程的可行解。

---

三 变形

「NOIP2012」同余方程

求关于 x的同余方程$ a x \equiv 1 \pmod {b}$的最小正整数解。

设$y·b + 1 = ax$，即$ax - by = 1$，则题目要求为找出满足上面等式的最小的正整数$x$。设$y_0 = - y$，变形为$ax + by_0 = 1$，似乎可以用exgcd处理。

考虑$\gcd(a,b)$的定义，$ax + by_0$一定是$\gcd(a,b)$的倍数。因$ax + by_0 = 1$，故$\gcd(a,b)|1$。因$\gcd(a,b) \geqslant 1$，故$\gcd(a,b) = 1$。那么上面的$ax + by_0 = 1$再变形为$ax + by_0 = \gcd(a,b)$。直接用exgcd求解就好了。

答案的处理
因exgcd可以求出上述方程的一组任意解，而题目要求是求出“最小正整数解”。根据解的关系，可知当$x_1$是解时，$x_1 \pm b$也是解。那么当$x \leqslant 0$时，另$x + b$直到$x > 0$；反之同理，即可求出最小正整数解。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;

#define LL long long

LL read(){
    LL s=0,ne=1; char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') ne=-1;
    for(;c>='0'&&c<='9';c=getchar()) s=(s<<1)+(s<<3)+c-'0';
    return s*ne;
}

LL a0,b0,x,y;

void exgcd(LL a,LL b){
    if(!b) return (void)(x=1,y=0);
    exgcd(b, a%b);
    int t = x;
    x = y;
    y = t-(a/b)*y;
}

int main()
{
    a0=read(); b0=read();
    
    exgcd(a0,b0);
    
    while(x < 0) 
        x += b0;
    x %= b0; //大于，直接取模
    printf("%d",x);
    
    return 0;
}