【算法】浅谈二元一次不定方程 (exgcd)

lnwhl · 2022-07-19 15:56:32 · 个人记录

模拟赛考了个 \operatorname{exgcd} 模板，小编打挂了，于是有了这篇文章。

Luogu P5656

给定一个二元一次不定方程 ax+by=c，求关于这个方程的解情况。

先判断无解，如果 c 不能整除 \gcd(a,b)，则一定无解。否则有解。

对于有解的情况，我们先用 \operatorname{exgcd} 求出

ax+by=\gcd(a,b)

一组特解 x_0,y_0。代码如下（马蜂挺阴间的）：

il ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1;y=0;
        return a;
    }
    ll r=exgcd(b,a%b,x,y);
    ll temp=x;
    x=y;
    y=temp-(a/b)*y;
    return r;
}//exgcd

故方程

ax+by=c

的特解为 x_1=\dfrac{x_0c}{\gcd(a,b)},y_1=\dfrac{y_0c}{\gcd(a,b)}。

易知解公差为 \dfrac{b}{\gcd(a,b)} 和 \dfrac{a}{\gcd(a,b)}，之后求出原方程的通解：

x=x_1+s\dfrac{b}{\gcd(a,b)}

y=y_1-s\dfrac{a}{\gcd(a,b)}

化简一下：

x=\dfrac{x_0c}{\gcd(a,b)}+s\dfrac{b}{\gcd(a,b)}=\dfrac{x_0c+sb}{\gcd(a,b)}

y=\dfrac{y_0c}{\gcd(a,b)}-s\dfrac{a}{\gcd(a,b)}=\dfrac{y_0c-sa}{\gcd(a,b)}

若 x,y>0，则需 -\dfrac{x_0c}{b}< s<\dfrac{y_0c}{a} \left\lceil\dfrac{-x_0c+1}{b}\right\rceil\le s\le\left\lfloor\dfrac{y_0c-1}{a}\right\rfloor
若 x,y\ge0，则需 -\dfrac{x_0c}{b}\le s\le\dfrac{y_0c}{a} \left\lceil\dfrac{-x_0c}{b}\right\rceil\le s\le\left\lfloor\dfrac{y_0c}{a}\right\rfloor

正整数解的个数即为 s_{\max}-s_{\min}+1。

若 -\dfrac{x_0c}{b}>\dfrac{y_0c}{a}，则无法满足 x,y 均为正整数。此时解的状况即为有整数解，无正整数解，x,y 的极值在 s 取极值时取到。

最后放一下垃圾代码。

#include <bits/stdc++.h>
#define ll long long
#define il inline
#define Rint register int 
#define ld long double
using namespace std;
int T; 
il ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
il void write(ll x)
{
    if(x<0){x=-x;putchar('-');}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
il ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1;y=0;
        return a;
    }
    ll r=exgcd(b,a%b,x,y);
    ll temp=x;
    x=y;
    y=temp-(a/b)*y;
    return r;
}//exgcd
int main()
{
    T=read();
    while(T--)
    {
        ll a,b,c,x=0,y=0;
        a=read(),b=read(),c=read();
        ll gcd=exgcd(a,b,x,y);
        if(c%gcd)
        {
            write(-1);putchar('\n');
            continue;
        }//1.判断无解 
        ld up=(y*c-1.0)/a,dn=(1.0-x*c)/b;
        ll smax=floor(up),smin=ceil(dn),ans=floor(up)-ceil(dn)+1;
        if(ans<=0)
        {   
            write((x*c+smin*b)/gcd);putchar(' ');
            write((y*c-smax*a)/gcd);putchar('\n');
        }
        else
        {
            write(ans);putchar(' ');
            write((x*c+smin*b)/gcd);putchar(' ');
            write((y*c-smax*a)/gcd);putchar(' ');
            write((x*c+smax*b)/gcd);putchar(' ');
            write((y*c-smin*a)/gcd);putchar('\n');
        }
    }
    return 0;
}