Gym 100963 Problem J: Finding positive coefficient using extended GCD

Revision en3, by BumbleBee, 2018-10-19 13:08:53

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?

Tags gcd, extended euclid

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English BumbleBee 2018-10-19 13:22:39 55
en5 English BumbleBee 2018-10-19 13:14:44 0 (published)
en4 English BumbleBee 2018-10-19 13:13:34 85
en3 English BumbleBee 2018-10-19 13:08:53 241
en2 English BumbleBee 2018-10-19 09:34:14 0 Tiny change: 'es: \n**$p > 0$** \n**$' -> 'es: \n**$$$p > 0$$$** \n**$'
en1 English BumbleBee 2018-10-19 09:32:31 1450 Initial revision (saved to drafts)