Linear Diophantine equation, Extended Euclidean Algorithm

Question

suppose i want to find any value of x and y such that they satisfy x . W + y . D = P

this can be done by the following using extended euclidean algorithm

int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
       x = 1;
       y = 0;
       return a;
    }
    int g, xi, yi;
    g = exgcd(b, a % b, xi, yi);
    x = yi;
    y = xi - (a / b * yi);
    return g;
}

but this will be just some random x and y satisfying the equation

suppose i add an additional constraint that i want any x y z such that

x>=0 y>=0 z>=0 and x + y + z = n

how can i effectively (please share code/pseudocode if possible) find all such x y and z??

my question boils down to find any x and y (using extended euclidean algorithm) which

1) satisfy a linear equation

2) fall in a given range

here is the link to the question if you want

Answer 1

Ok so we have 2 equations and 3 unknowns, so doing some simple mathematics we can find the equations we need to solve

x * W + y * D + z * 0 = p

And

x + y + z = n 

given

x,y,z >=0

So firstly we will reduce one unknown by looping through any one of the unknowns lets say z

We iterate through 0 - n for z and our new equations will be

x * w + y * d = p

And

x + y = m   { m is n - z for value of z in current iteration

Now we have 2 equations and 2 unknowns

So our solution for x and y can now be reduced by substituting x in first equation

Which makes it

(m - y) * w + y * d = p

This can be reduced to

y = (p - m * w) / (d - w)

and

x = m - y

You can stop at first value where x and y are integers