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

yangrunze · 2020-03-24 19:45:46 · 题解

先说两句：

1. 本题解学习了编程&\LaTeX神仙 \color{black}{\text{离}}\color{red}\text{散小波变换\degree} 的思路，让我们一起%ta！（管理员：题解抄袭题解，棕了！）
2. 在阅读本文之前，如果你已经学会了exgcd的基础用法，并且AC P1082 同余方程，那就更好啦！

没有做到也没关系，让我们先来了解一下exgcd的基础用法：

exgcd算法，听名字就知道跟辗转相除法求\gcd有关，我们用的就是辗转相除法的核心式子：

exgcd：求ax+by=\gcd(a,b)的整数解

设\gcd(a,b)=d

则ax+by=d

我们设已经找到了一组解x',y'，使bx'+(a \bmod b)y'=\gcd(a,b)

由于商\times除数+余数=被除数，a\bmod b可以这么表示：

给它稍微变个形：

和原式对比一下，你会惊奇地发现：

由于b=0时\begin{cases}x=1\\y=0\end{cases}，所以递归求解即可

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll x,y; 
void exgcd(ll a,ll b){
    if(b==0){
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b);
    ll t=x;
    x=y;
    y=t-a/b*y;
}
int main(){
    ll a,b;
    cin>>a>>b;
    exgcd(a,b);
    cout<<(x%b+b)%b;
}

以上就是最基础的exgcd啦！但是我们肯定不能只满足于这些，接下来

正 片 开 始

……题目看样子好难鸭……

没关系，咱们一个一个来看！

若该方程无整数解，输出 -1

这个很好办，根据裴蜀定理，如果c不是gcd(a,b)的倍数，方程必定无解

（不了解裴蜀定理的小伙伴戳这，本文有很多地方也cv自这篇文章）

接下来，用exgcd求出ax+by=\gcd(a,b)的整数解之后，就是各种整数解的讨论啦！

把大象关进冰箱里要分三步，那么要解一个二元一次不定方程要分几步呢？也是三步

首先，咱们来想这样一个问题，

step 1.用ax+by=\gcd(a,b)的整数解来求ax+by=c的整数解

这就非常简单了，咱还是设 \gcd(a,b)=d

由于d是a和b的最大公因数，所以d肯定能被他俩整除

从刚才的得到的结论出发，我们设已知ax'+by'=d，d\times q=c

两边同时乘q，这样的话就可以发现ax'\times q+by'\times q=d\times q，即ax'\times q+by'\times q=c

step 2.用这组解x_0,y_0找出方程所有的解

咱们还是先从这组解x_0,y_0出发，设a(x_0+m)+b(y_0+n)=c

这样的话我们只需要求出m和n就好啦

从这个式子出发：a(x_0+m)+b(y_0+n)=c

展开它：ax_0+am+by_0+bn=c

那只要让am+bn=0，那就没问题啦！

继续设\gcd(a,b)=d，我们让\begin{cases}m=t\times \dfrac{b}{d}\\n=-t\times \dfrac{a}{d}\end{cases}

带进去算一下am+bn得到\dfrac{ab}{d}-\dfrac{ab}{d}，果然是0！

任取一个t，就可以算出相应的m，n，进而推出x和y，通解get！

step 3：考虑最大/最小值

这一步是重难点，竖起耳朵认真听哟！

首先，\begin{cases}x=x_0+t\times \dfrac{b}{d}\\y=y_0-t\times \dfrac{a}{d}\end{cases}

可以看出，当t增大的时候，x越来越大，y越来越小

由于增加/减少的值太难写了，接下来设t\times \dfrac{b}{d}为t_x，-t\times \dfrac{a}{d}为t_y，也就是\begin{cases}x=x_0+t_x\\y=y_0+t_y\end{cases}

接下来，我们需要找出x的最小整数解x_{\min}，只需要把x_0减去好多好多个t就好

那到底减多少呢？

既然是正整数，那就要求x_{\min}\geq 1，设减去k个t，就可以得到：

接下来就是解一元一次不等式啦！

两边同时除以t，因为这里要求x越来越小，所以t要小于0，注意要变号哟！

因为这边必须大于这个值，所以要取上整

这样的话，我们就可以得到x_{\min}，也就是x_0-\lceil\dfrac{1-x_0}{t_x}\rceil啦！

通过刚才的分析呢，x_{\min}对应的y值正好是y_{\max}，如果y_{\max}<0呢，那就没有正整数解啦！

（没有整数解的话，我们还需要把y_{\min}求出来，这个就和刚才处理x_{\min}的方法一样了，y_{\min}=y_0-\lceil\dfrac{1-y_0}{t_y}\rceil）

搞定了两个解，接下来咱们在搞剩下的两个：x_{\max}和y_{\min}

先来看y_{\min}：我们需要将y_{\max}减去尽可能多的t_y，使其为正整数

有没有发现一个神奇的事情？我们要求的y_{\min}，正好就是y_{\max}\bmod t_y！不过为了防止0之类的特殊情况，我们还是把它写成(y_{\max}-1)\bmod t_y+1

那我们的x_{\max}呢？很简单，只要加上和y_{\max}减去的相同的t_x就行惹，也就是x_{\min}+\lfloor \dfrac{y_{\max}-1}{t_y}\rfloor\times t_x

最后还剩下一个解的个数，还是看y_{\max}减到y_{\min}的过程，可以有\lfloor \dfrac{y_{\max}-1}{t_y}\rfloor+1个解

总结一下就是这样的：

放码过来呀！

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;//十年OI一场空，不开long long见祖宗
ll x,y;
inline ll read(){//卡常卡得好，快读不能少
    char c=getchar();
    int f=1;
    ll x=0;
    while(c<'0'||c>'9'){
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
    return x*f;
} 
inline ll exgcd(ll a,ll b){//来一份萌萌哒exgcd
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll d=exgcd(b,a%b);
    ll t=x;
    x=y;
    y=t-a/b*y;
    return d;//顺便把最大公因数也给求出来了呢！
}
int main(){
    ll t=read();
    while(t--){
        ll a=read(),b=read(),c=read();
        ll d=exgcd(a,b);//求出d
        if(c%d){//不满足裴蜀定理，直接输出-1
            printf("-1\n");
            continue;
        }
        x=x*c/d,y=y*c/d;//求出x0和y0，tx和ty
        ll tx=b/d,ty=a/d;
        ll k=ceil((1.0-x)/tx);//求出k
        x+=tx*k;
        y-=ty*k;    
        if(y<=0){//如果没有正整数解，算出ymin之后输出
            ll ymin=y+ty*1ll*ceil((1.0-y)/ty);
            printf("%lld %lld\n",x,ymin);
        }
        else{//按照刚才说的处理
            printf("%lld ",(y-1)/ty+1);
            printf("%lld ",x);
            printf("%lld ",(y-1)%ty+1);
            printf("%lld ",x+(y-1)/ty*tx);
            printf("%lld\n",y);
        }
    }
    return 0;
}

The end