二元一次不定方程(exged)

题目概要

给定二元一次不定方程ax+by=c
若该方程无整数解，输出 -1
若该方程有整数解，且有正整数解，则输出其正整数解的数量，所有正整数解中 x 的最小值，所有正整数解中 y 的最小值，所有正整数解中 x 的最大值，以及所有正整数解中 y 的最大值
若方程有整数解，但没有正整数解，你需要输出所有整数解中 x 的最小正整数值， y 的最小正整数值

正整数解即为 x,y 均为正整数的解
整数解即为 x,y 均为整数的解
x 的最小正整数值即所有 x 为正整数的整数解中 x 的最小值，y 同理

数据范围：1<=a,b,c<=1e9 ，输入含有多组数据，数据组数不超过2*10^5

样例输入：
2
2 11 100
3 18 6

样例输出:
4 6 2 39 8
2 1

拓展欧几里得算法

扩展欧几里得算法：用于求解形如ax+by=gcd(a,b)的不定方程特解。
求解方法&证明： 当b=0时，可以看出gcd(a,b)=a，而x=1,y=0是方程的一组特解
当b!=0时，根据欧几里得算法递归求解exgcd(b,a%b,x,y)，设a’=b,b’=a%b,可以求得a’x’+b’y’=gcd(a,b)的一组特解，即x’,y’。
而ax+by=gcd(a,b)=a’x’+b’y’,将a’=b,b’=a%b代入，得x=y’,y=x-a/b*y’。

Code

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

求二元一次方程组的特解

二元一次方程：对于形如ax+by=c的二元一次方程，裴蜀定理指出，当且仅当gcd(a,b)|c(|为整除)时，存在整数解。由裴蜀定理我们可以得到一个推论：a,b互质的充要条件是存在整数x,y使ax+by=1.
设g=gcd(a,b),a’=a/g,b’=b/g,c’=c/g,则ax+by=c⇔a’x+b’y=c’，
此时gcd(a’,b’)=1,可以利用exgcd求出a’x’+b’y’=1的一组特解，继而得出x=c’y’, y=c’x’,从而得到ax+by=c的一组特解

线性同余方程：对于形如ax\equiv≡c(mod b)的线性同余方程，根据模运算的定义，在方程左侧添加一个by不会对结果造成影响，其实质就等价于ax+by=c的不定方程，利用上述方法求解便可。

求二元一次方程/线性同余方程通解

设g=gcd(a,b), a’=b/g, b’=a/g， x0,y0为方程的一组特解，则通解为x=x0+a’t, y=y0-b’t(t为整数)

证明
Q:为什么它是通解？
A:因为将该解代入方程恒成立
Q:但还有其他形式的解能满足，例如x=x0+bt, y=y0-at,为什么选他呢?
A:因为他能无遗漏地表示所有正整数解，因为lcm(a,b)=ab/g, x,y的系数分别为a,b,所以x,y的在满足方程的前提下的最小变化量为b/g,a/g,证毕。
线性同余方程同理

解决问题

至此我们具备了解决问题所需要的所有知识
无整数解： 要求输出-1。根据扩展欧几里得算法的定义可得，当c%gcd(a,b)≠0时方程无整数解，输出-1即可。
判断有无正整数解： 根据二元一次方程的通解可得，x,y的增减性相反，所以若存在正整数解，则当x取得最小正整数解时，y取得最大正整数解，若此时y≤0,则说明该方程无正整数解。最小整数解可以通过取余快速得到，如x的最小整数解为(x0%a’+a’)%a’,这里需要特判下，当x=0时另x=a’,y同理。
解组个数： 易得正整数解的组数为(Xmax-Xmin)/a’+1或(Ymax-Ymin)/b’+1.

Code：

#include<cstdio>
#define ll long long    //注意开long long

ll read(){
    char ch;
    ll num=0;
    ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9'){
        num=num*10+ch-'0';
        ch=getchar();
    }
    return num;
}

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

int main(){
    ll n,x,y,a,b,c,d;
    n=read();
    while(n--){
        a=read(), b=read(), c=read();
        d=ex_gcd(a,b,x,y);
        if(c%d!=0){
            printf("-1\n");
            continue;
        }
        x*=c/d, y*=c/d;
        ll temp=(x%(b/d)+b/d)%(b/d);    //temp为x的最小正整数解
        if(temp==0)                //特判
            temp=b/d;
        if((c-a*temp)/b<=0){
            int q=(y%(a/d)+a/d)%(a/d);    //q为y的最小正整数解
            if(!q)
                q=a/d;
            printf("%lld %lld\n",temp,q);
            continue;
        }
        ll temp2=(y%(a/d)+a/d)%(a/d);    //temp2为y的最小正整数解
        if(!temp2)
            temp2=a/d;
        int maxx=(c-temp2*b)/a;        //maxx为x的最大正整数解
        printf("%lld %lld %lld %lld %lld\n",(maxx-temp)/(b/d)+1,temp,temp2,maxx,(c-temp*a)/b);
    }
    return 0;
}

此题为洛谷P5656，建议去洛谷切下这道题来巩固，洛谷CF7C Line为弱化版，只用找出一组整数解即可

求解二元一次方程