扩展欧几里得(exgcd)-求解不定方程求逆元

贝祖定理

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

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

有一个直接的应用就是如果 $a x + b y = 1$ 有解，那么 $g c d (a, b) = 1$ 。

然而这并不能告诉我们x,y解是多少。

扩展欧几里得（exgcd）

首先对 $a | b$ 一定有一个解 $a \times 1 + b \times 0 = gcd (a, b)$ 。但是我们的 $a$ 和 $b$ 不一定满足该条件。不过我们可以辗转相除直到满足条件，然后回代：

$\begin{aligned} b \times x_{n} + (a - ⌊ \frac{a}{b} ⌋ * b) \times y_{n} = gcd (a, b) \\ \Rightarrow & a \times y_{n} + b \times (x_{n} - ⌊ \frac{a}{b} ⌋ \times y_{n}) = gcd (a, b) \\ \Rightarrow & x_{n + 1} = y_{n}, y_{n + 1} = x_{n} - ⌊ \frac{a}{b} ⌋ \times y_{n} \end{aligned}$

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)//这个是返回值版的 
{
    if(!b)
    {
        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;    //更改x和y的值，因为是引用的
    return r;     //得到a b的最大公因数
}
void exgcd1(ll a,ll b,ll &d,ll &x,ll &y)//这个不返回直接更新 
{
    if(!b)d=a,x=1,y=0;
    else
    {
        exgcd1(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}
int main()
{
    ll a,b,d,x,y;
    cin>>a>>b;
    d=exgcd(a,b,x,y);//最大公约数
//    exgcd1(a,b,d,x,y); 
    printf("%d %d",x,y);//x，y已经被更新了 
    return 0;
}

解释一下 exgcd1() 的递推式。d 是最大公约数，这个在 b=0，即上一层 a%b==0 时找到，更新传回即可。

我们 x 和 y 都是直接更新地址的，那我们这里的 y 其实就是传给上一层的 x，相当于 y=x-(a/b)*y，因为我们传下来的时候是将 x 和 y 颠倒的，那么这里 x 就和 y 互换,即 y-=(a/b)*x，x 还是 x，传上去就变成 y 了。

求逆元

上面得到的 $x$ 即为 $a$ 在 $(\mod b)$ 意义下的逆元。

注意，一个数的是有可能没有逆元的，需要提前判断，否则这时候 x 好像是返回 $1$ 。如果是有逆元的，解出来的 x 有可能是负数，这时候你可能需要 x=(x+mod)%mod。

求不定方程

（我之前没用Markdown写得真难受）

（这个部分是我学了excrt之后才更新的）

（之前学的真是肤浅而且一团乱麻）

exgcd 既然可以求 $a x + b y = gcd (a, b)$ 的解，那么一定就可以求 $a x + b y = c$ 的解。

假设 $g = gcd (a, b)$ ，那么我们先把方程两边同时乘 $g / c$ ，那么是不是就可以求 $x$ 和 $y$ 了呢？那么求完之后我们在给他乘回去不就行了？

那就行了。

判断无解的情况：如果求出来的 $g$ 并不能被 $c$ 整除，说明在数论范围内它无解。

鉴于不定方程的性质， $x$ 的最小正整数解是在 $b$ 意义下取模的， $y$ 的最小正整数解是在 $a$ 意义下取模的。我们就可以求出 $x$ ， $y$ 的最小整数解和整数解的个数。因为 $x$ 和 $y$ 的增减性是相反的，我们也就可以相应算出最大值。

P5656 【模板】二元一次不定方程 (exgcd)

#include<bits/stdc++.h>
#define int long long //watch out!
using namespace std;
inline int read()
{
    int x=0,w=0;char c=getchar();
    while(!isdigit(c))w|=c=='-',c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x)
{
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline void exgcd(int a,int b,int& d,int& x,int& y){
    if(!b)d=a,x=1,y=0;
    else exgcd(b,a%b,d,y,x),y-=(a/b)*x;
}
inline void solve(int a,int b,int c)
{
    int cnt=0,miny,maxy,minx,maxx;
    int gcd,x,y;
    exgcd(a,b,gcd,x,y);
    if(c%gcd!=0){printf("-1\n");return;}
    a/=gcd;b/=gcd;c/=gcd;//这里学习了一下大佬的做法，将所有答案除以gcd，实际上是一样的，不过下面的x和y就不是乘c/gcd了。
    x*=c;
    y*=c;
    minx=x>0&&x%b!=0?x%b:x%b+b;
    maxy=(c-minx*a)/b;
    miny=y>0&&y%a!=0?y%a:y%a+a;
    maxx=(c-miny*b)/a;
    if(maxx>0)cnt=(maxx-minx)/b+1;
    if(cnt==0)printf("%d %d\n",minx,miny);
    else printf("%d %d %d %d %d\n",cnt,minx,miny,maxx,maxy);
}
signed main()
{
    int t=read();
    while(t--){
        int a=read(),b=read(),c=read();
        solve(a,b,c);
    }
    return 0;
}

扩展欧几里得(exgcd)-求解不定方程 求逆元

贝祖定理

扩展欧几里得（exgcd）

求逆元

求不定方程

扩展欧几里得(exgcd)-求解不定方程求逆元