Re：Exgcd解二元不定方程

模拟又炸了，我死亡

$exgcd$（扩展欧几里德算法）用于求$ax+by=gcd(a,b)$中$x,y$的一组解，
它有很多应用，比如解二元不定方程、求逆元等等，
这里详细讲解一下$exgcd$的原理。

了解$exgcd$算法前，需要$gcd$算法做铺垫。gcd，又称辗转相除法，用于计算两个整数 $a,b$ 的最大公约数。

$gcd$函数的基本性质：

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

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

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

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

证明一下第四条：

设$k$为整数

设$gcd(a,b) = d$

$a$ $mod$ $b=a-kb$，$k = a/b$

因为$a$ $mod$ $d=0,b$ $mod$ $d=0$

所以$kb$ $mod$ $d=0$,

$a-kb$ $mod$ $d=0$

即$(a$ $mod$ $b)$ $mod$ $d=0$

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

　　gcd　　

理解了$gcd$，再来证明为什么$exgcd$可以求出$ax+by=gcd(a,b)$的$x,y$。

当$b=0$时，$gcd(a,b) = a$，$ax+by$ 即 $a*1 + 0*0 = gcd(a,b)$；

$x=1,y=0$（因为$b = 0$，$y$的值其实不重要，这里就写成$0$）

因为$gcd(a,b) = ax+by$，$gcd(b,a$ $mod$ $b) = ax'+ by'$，

每次递归时，$gcd(a,b) = gcd(b,a$ $mod$ $b)$，所以$ax+by = ax'+ by'$，

并且已知 $a%b = a-(a/b)*b$，那么可以得到

$ax'+ by'$

$= bx + (a$ $mod$ $b)y $

$= bx + (a-a/b*b)y $

$= bx + ay - (a/b)*by $

$= ay + b(x-(a/b)*y) $

$x'=y$； $y'=x-(a/b)*y $

int exgcd(int a,int b,int &x, int &y) {
    if(b == 0) {
        x=1,y=0;
        return a;
    }
    int ans = exgcd(b,a%b,x,y);
    int tx = x;
    x = y;
    y = tx-a/b*y;
    return ans;
}

　　exgcd　　

明白了$exgcd$的原理，思考它如何求解形如$ax+by=c$的不定方程。

设$k$为整数，

设$c=k*gcd(a,b)$

$ax+by=gcd(a,b)$，

两边同乘$k$，得

$k*ax+k*by=k*gcd(a,b)=c$

所以$c$一定为$gcd(a,b)$的倍数。若$c$ $mod$ $gcd(a,b) ≠ 0$，则方程无整数解。

此时的$x'=kx=c/gcd(a.b)*x$。

可以发现，$ax+by=c$

(x \in Z

这个定理叫做裴蜀定理

。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define MogeKo qwq
using namespace std;

int n,x,sum;

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

int main() {
    scanf("%d",&n);
    sum = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d",&x);
        if(x < 0) x = -x;
        sum = gcd(sum,x);
    }
    printf("%d",sum);
    return 0;
}

裴蜀定理

那么，怎么保证x是最小正整数呢？

设$k$为整数，　　　

　　　$ax+by$

　　$= ax + by + k*ab - k*ab$

　　$= a(x+kb) + b(y-ka)$

也就是说，当$x$改变$b$的整数倍时，原式的值可以保持不变；

那么最小正整数即为$x$ $mod$ $b$；

但是要考虑$x$为负数的情况，就要先将$x$加上$b$，直到$x$为正数，再取模，可以得到$x = (x$ $mod$ $b+b)$ $mod$ $b$

综上所述，

$x=(x*c/gcd(a,b)$ $mod$ $b+b)$ $mod$ $b$

int exgcd(int a,int b,int &x, int &y) {
    if(b == 0) {
        x=1,y=0;
        return a;
    }
    int ans = exgcd(b,a%b,x,y);
    int tx = x;
    x = y;
    y = tx-a/b*y;
    return ans;
}

int main() {
    scanf("%d%d%d",&a,&b,&c);
    if(a<0) {
        a = -a;
        c = -c;
    }
    exgcd(a,b,x,y);
    if(c%ans!=0)
        printf("Impossible");
    else
        printf("%d",(x*(c/ans))%(b/ans)+(b/ans))%(b/ans));
        return 0;
}

　　解二元不定方程　

模板题：Luogu P1516 青蛙的约会

设跳了$X$次，

由题意得，$m*X+x=n*X+y$ $(mod$ $l)$

$(m-n)*X=y-x$ $(mod$ $l)$

$(m-n)*X-l*Y=y-x$

令$m-n=a$,$l=b$,$y-x=c$,$Y=-Y$

则有$aX+bY=c$

注意负数的情况：若$m-n<0$，则变成了前面的追后面的

$a=n-m$,$c=(x+l-y)$ $mod$ $l=x-y$

即$a=-a,c=-c$

#include<cstdio>
#define int long long
int x,y,m,n,l,a,b,c,x0,y0,g,tmp;

int exgcd(int a,int b,int &x, int &y) {
    if(b == 0) {
        x=1,y=0;
        return a;
    }
    int ans = exgcd(b,a%b,x,y);
    int tx = x;
    x = y;
    y = tx-a/b*y;
    return ans;
}

main() {
    scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);
    a=n-m;
    b=l;
    c=x-y;
    if(a<0)
        a=-a,c=-c;
    int g = exgcd(a,b,x0,y0);
    if(c%g!=0)
        printf("Impossible");
    else 
        printf("%lld",(c/g*x0%(b/g)+b/g)%(b/g));
}

View Code