欧几里得算法

  • 求最大公约数
int gcd(int a, int b) {
    while (b) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
  • 求最小公倍数
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

扩展欧几里得算法

  • 贝祖定理

    • 即如果a、b是整数，那么一定存在整数x、y使得ax+by=gcd(a,b)。

    • 得到x,y后，可以将x+b，y-a,结果不变

    • 换句话说，如果ax+by=m有解，那么m一定是gcd(a,b)的若干倍。（可以来判断一个这样的式子有没有解）

    • 有一个直接的应用就是 如果ax+by=1有解，那么gcd(a,b)=1；

  • 证明

    • 当到达递归边界的时候，b==0，a=gcd(a,b) 这时可以观察出来这个式子的一个解：a1+b0=gcd(a,b)，x=1,y=0，注意这时的a和b已经不是最开始的那个a和b了，所以我们如果想要求出解x和y，就要回到最开始的模样。

    • 初步想法：由于是递归的算法，如果我们知道了这一层和上一层的关系，一层一层推下去，就可以推到最开始的。类似数学上的数学归纳法。

    • 假设当前我们在求的时a和b的最大公约数，而我们已经求出了下一个状态：b和a%b的最大公因数，并且求出了一组x1和y1使得                          b*x1+(a%b)*y1=gcd

    • （注意在递归算法中，永远都是先得到下面一个状态的值）

    • 这时我们可以试着去寻找这两个相邻状态的关系：

    • 首先我们知道：

a%b=a-(a/b)*b；带入：

b*x1 + (a-(a/b)*b)*y1

= b*x1 + a*y1 – (a/b)*b*y1

= a*y1 + b*(x1 – a/b*y1) = gcd 
 
 发现 x = y1 , y = x1 – a/b*y1

  • 这样我们就得到了每两个相邻状态的x和y的转化，就可以在求gcd的同时对x和y进行求值了

  • 模板

int exgcd(int a, int b, int &x, int &y) {//扩展欧几里得算法
    if (b == 0) {
        x = 1;
        y = 0;
        return a;  //到达递归边界开始向上一层返回
    }
    int r = exgcd(b, a % b, x, y);
    int temp = y;    //把x y变成上一层的
    y = x - (a / b) * y;
    x = temp;
    return r;     //得到a b的最大公因数
}

题目

洛谷1082同余方程
image.png

  • 直接枚举肯定会超时，我们所以我们要考虑ext-gcd

  • 我们考虑ax+by=1，对此式左右两方同时mod b，那么一定有 ax=1(mod b)
    但是求得了x还不一定满足题目要求，可能是负数，还可能太大，我们再将其多次加上或者减去b直到满足要求即可。 x=((x%b)+b)%b;

int x, y, c, d;

int main() {
    scc(c, d);
    exgcd(c, d, x, y);
    x = ((x % d) + d) % d;
    p(x);
    return 0;
}

hhhhh