I was trying to solve problem J of this gym contest.

In short, I am given non-negative integers n, m, a and k. I have to find such integers p and q that satisfies:
p > 0
q >  - 1
k + pa = n + qm

I wrote the third equation in this way:
pa + ( - q)m = n - k

Then using extended GCD I found such integers x and y that,
xa + ym = g, where g = GCD(a, m)

Multiplying (n - k) / g on both side we get:
[x(n - k) / g]a + [y(n - k) / g]m = n - k

Finally, I get p = x(n - k) / g and q =  - y(n - k) / g

The problem is, my implementation of extended GCD finds such x and y that resulting p and q violates the constraints p > 0 and q >  - 1.

For example, if n = 3, m = 5, a = 2 and k = 2, using extended GCD I am getting:
x =  - 2, y = 1 and then p = x(n - k) / g =  - 2, q =  - y(n - k) / g =  - 1.

But I need to find x = 3, y =  - 1 so that I can get p = x(n - k) / g = 3, q =  - y(n - k) / g = 1.

Here is my implementation of extended GCD:

int gcdExt(int a,int b,int &x,int &y)
{
    if (a==0){
        x=0,y=1;
        return b;
    }
    int p,q;
    int r=gcdExt(b%a,a,p,q);
    x=q-(b/a)*p,y=p;
    return r;
}

How can I change this function to find coefficients x and y that give such p and q that satisfies given constraints?