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?