### BumbleBee's blog

By BumbleBee, history, 12 months ago, ,

I am 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 Euclidean algorithm 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 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 Euclidean algorithm:

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?

• +3

 » 12 months ago, # |   +4 If you have the solution (x, y) for the equation ax - by = 1 then any other solution (x', y') can be expressed as x' = x + kb, y' = y + ka for some integer value k.