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

贝祖定理

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

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

有一个直接的应用就是如果 \(ax+by=1\) 有解，那么 \(gcd(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-\lfloor \frac ab\rfloor*b)\times y_n=\gcd(a,b) \\ \Rightarrow &a\times y_n + b\times(x_n – \lfloor \frac ab\rfloor\times y_n) = \gcd(a,b)\\ \Rightarrow &x_{n+1} = y_n , y_{n+1} = x_n – \lfloor \frac ab\rfloor\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\) 在 \(\pmod b\) 意义下的逆元。

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

求不定方程

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

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

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

exgcd 既然可以求 \(ax+by=\gcd(a,b)\) 的解，那么一定就可以求 \(ax+by=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)-求解不定方程求逆元