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.

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?

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;

}

I just solved this problem, here is my solution.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const char nl = '\n';

/*
returns the gcd(a, b) and at the same time, 
solves the linear combination: a*x + b*y = gcd(a, b)
for integers x, y.
*/
ll extgcd(ll a, ll b, ll& x, ll& y) {
    x = 1, y = 0;
    ll x1 = 0, y1 = 1, a1 = a, b1 = b;
    while (b1) {
        ll q = a1 / b1;
        tie(x, x1) = make_tuple(x1, x - q * x1);
        tie(y, y1) = make_tuple(y1, y - q * y1);
        tie(a1, b1) = make_tuple(b1, a1 - q * b1);
    }
    return a1;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    ll n, m, a, k, xg, yg, x0, y0, g, c, shift;
    while(true)
    {
        cin >> n >> m >> a >> k;
        if(n == 0 && m == 0 && a == 0 && k == 0)
            return 0;
        // because the man can only reach for the first time at k + a
        k += a;
        // this ensures a situation where the man starts after the woman
        if(k < n)
        {
            swap(n, k), swap(m, a);
        }
        // check for solution to diophantine equation
        g = extgcd(a, m, xg, yg);// yields: a*xg + m*yg = gcd(a, m)
        c = k - n;
        if(c % g != 0)
        {
            cout << "Impossible\n";
            continue;
        }
        // now: a*x0 + m*y0 = c
        x0 = xg * c / g, y0 = yg * c / g;
        
        // shift x0 so that |x0| is at a minimum and x0 < 0
        // equivalently, shifting y0 so that |y0| is at a minimum and y0 > 0
        if(x0 > 0)
        {
            shift = (x0 * g + m - 1) / m;
            x0 -= shift * m / g;
            y0 += shift * a / g;
        }
        else
        {
            shift = (-x0 * g) / m;
            x0 += shift * m / g;
            y0 -= shift * a / g;
        }
        assert(k - x0 * a == n + y0 * m);
        cout << n + y0 * m << nl;
    }
}

I know that this is a very old post, but i would like to help other people like me that also want to better understand the solution to this problem.

To simple began the solution, its good to observe that we want to find x and y with some constraints that solve this equation :

$$$k+a*x=n+m*y$$$

$$$x \geq 1, x \in Z$$$

$$$y \geq 0, y \in Z$$$

x must be greater or equal than 1 because when x equals to 0, the man approaches and not stretches, and x < 0 does not make sense.

y must be greater or equal than 0 because when y equals to 0, the woman already stretches, and y < 0 does not make sense.

Also observe that we can write the above equation in another way:

$$$a*x-m*y=n-k$$$

And also:

$$$a*x+(-m)*y=n-k$$$

And this type of equation can be solved simply using the extend euclidean algorithm, see the link.

Observe that we don't have answer if n-k is not a multiple of $$$gcd(a,-m)$$$.

Unfortunately, sometimes x, and y could be negative, but observe that:

$$$0 = a*\frac{-m}{gcd(a,-m)}+(-m)*\frac{a}{gcd(a,-m)}$$$

And use that to change x and y without affect the answer.

See my code below

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll gcd(ll a, ll b, ll* x, ll* y){
    if(b == 0){
        *x = 1;
        *y = 0;
        return a;
    }
    ll x1, y1;
    ll g = gcd(b, a%b, &x1, &y1);
    *x = y1;
    *y = x1-y1*(a/b);
    return g;
}

int main(){

    while(1){

        ll n, m, a, k;
        cin >> n >> m >> a >> k;

        if(n==0 && m==0 && a==0 && k==0){
            break;
        } 

        ll x, y;
        ll g = gcd(a, -m, &x, &y);

        ll dif = n-k;

        if(dif%g!=0){
            cout << "Impossible\n";
            continue;
        }
        
        if(g < 0){
            x = -x, y = -y, g = -g;
	}

        x = x*(dif/g);
        y = y*(dif/g);

        ll d = m/g;

        if(x <= 0){
            ll mult = (abs(x)/d)+1;
            x += d*mult;
        }else{
            ll mult = (x-1)/d;
            x -= d*mult;
        }

        cout << k+a*x << endl;

    }

    return 0;
}

I am getting WA on test case 2 Can someone help me in which case my code is getting wrong My Approach: get initial solutions to equation mx+ay=k+a-n and then shift the solutions using x'=x+kg/a and y=y-kg/m to get both x and y greater than zero

code: 174696154

lost a day on it because using it instead of long long on some variables.