Auto comment: topic has been updated by devarshi09 (previous revision, new revision, compare).

https://cp-algorithms.com/algebra/linear-diophantine-equation.html

Just modify the find_all_solutions function.

Same here. Here's what I have: Lets say $$$y$$$ is the answer. $$$y \equiv n \mod m$$$ and $$$y \equiv k \mod a$$$. So we have to find $$$x$$$ such that $$$n + xm \equiv k \mod a$$$. The answer would be $$$n + xm$$$. This is a Diophantine equation of the form $$$xm - ax' = k - n$$$.

I'm also trying to find the smallest $$$y$$$ such that $$$y >= max(n, k+a)$$$. I do that by generating new solutions for the Diophantine equation.

Now, I don't know what happens when $$$a = 0$$$ or $$$m = 0$$$. I suppose I have to print $$$\textit{Impossible}$$$ here but I can't get the AC yet. Same thing for $$$n = 0$$$ or $$$k = 0$$$. A little help here would be nice.

I'm also unable to solve this problem and cant find an editorial on this anywhere.Can someone who solved this please post the solution?

please help me with this question i am unable to understand how extended gcd algorithm will help me

Hey did you solve this? Because I am unable to solve it by extended euclidean algorithm or by any other means

include<bits/stdc++.h>

using namespace std;

define FastIO ios_base::sync_with_stdio(false); cin.tie(0);

define ll long long

define ull unsigned long long

define pb push_back

define All(x) (x).begin(),(x).end()

define mp make_pair

define nl "\n"

typedef pair<int,int>ii; typedef vectorvi; typedef vectorvii; typedef vectorvvi; typedef vectorvl; typedef vector vvl; template void print(T& a) { for(auto x:a) cout<<x<<" "; cout<<"\n"; }

ll gcd(ll a, ll b, ll& x, ll& y) { if(b==0) { x=1; y=0; return a; }

ll x1,y1,g;

g=gcd(b,a%b,x1,y1);

x=y1;
y=x1-((a/b)*y1);

return g;

}

bool anys(ll a, ll b, ll& x, ll &y, ll c,ll& g) { g=gcd(a,b,x,y);

if(c%g)
    return false;

x*=(c/g);
y*=(c/g)*(-1);

return true;

}

void ss(ll a, ll b, ll& x, ll& y,ll cnt) { x+=(cnt*b); y+=(cnt*a); }

bool alls(ll a, ll b, ll& x, ll& y, ll c) { ll cnt,g;

if(!anys(a,b,x,y,c,g))
    return false;

a/=g;
b/=g;

if(b>0)
{
    ss(a,b,x,y,(0-x)/b);

    if(x<0)
    {
        x+=b;
        y+=a;
    }
}

if(a>0  && y<0)
{
    ss(a,b,x,y,(0-y)/a);

    if(y<0)
    {
        x+=b;
        y+=a;
    }

}

if(x<0 || y<0)
    return false;

else return true;

}

int main() {

FastIO

while(1)
{
    ll n,m,a,k,c,x,y;
    cin>>n>>m>>a>>k;

    if(n+m+k+a==0)
        break;

    c=k+a-n;

    if(c==0)
        cout<<n<<nl;

    else if(a==0 && m==0)
        cout<<"Impossible"<<nl;

    else
    {
        bool flag=alls(m,a,x,y,c);

        if(flag)
            cout<<(m*x)+n<<nl;

        else cout<<"Impossible"<<nl;
    }

}

return 0;

}