How to solve Linear Diophantine equations in programming?

Question

I have read about Linear Diophantine equations such as ax+by=c are called diophantine equations and give an integer solution only if gcd(a,b) divides c.

These equations are of great importance in programming contests. I was just searching the Internet, when I came across this problem. I think its a variation of diophantine equations.

Problem :

I have two persons,Person X and Person Y both are standing in the middle of a rope. Person X can jump either A or B units to the left or right in one move. Person Y can jump either C or D units to the left or right in one move. Now, I'm given a number K and I have to find the no. of possible positions on the rope in the range [-K,K] such that both the persons can reach that position using their respective movies any number of times. (A,B,C,D and K are given in question).

My solution:

I think the problem can be solved mathematically using diophantine equations.

I can form an equation for Person X like A x_1 + B y_1 = C_1 where C_1 belongs to [-K,K] and similarly for Person Y like C x_2 + D y_2 = C_2 where C_2 belongs to [-K,K].

Now my search space reduces to just finding the number of possible values for which C_1 and C_2 are same. This will be my answer for this problem.

To find those values I'm just finding gcd(A,B) and gcd(C,D) and then taking the lcm of these two gcd's to get LCM(gcd(A,B),gcd(C,D)) and then simply calculating the number of points in the range [1,K] which are multiples of this lcm.

My final answer will be 2*no_of_multiples in [1,K] + 1.

I tried using the same technique in my C++ code, but it's not working(Wrong Answer).

This is my code : http://pastebin.com/XURQzymA

My question is: can anyone please tell me if I'm using diophantine equations correctly ?

If yes, can anyone tell me possible cases where my logic fails.

These are some of the test cases which were given on the site with problem statement.

A B C D K are given as input in same sequence and the corresponding output is given on next line :

2 4 3 6 7

3

1 2 4 5 1

3

10 12 3 9 16

5

This is the link to original problem. I have written the original question in simple language. You might find it difficult, but if you want you can check it:

http://www.codechef.com/APRIL12/problems/DUMPLING/

Please give me some test cases so that I can figure out where am I doing wrong ?

Thanks in advance.

Answer 1

Solving Linear Diophantine equations

ax + by = c and gcd(a, b) divides c.

1. Divide a, b and c by gcd(a,b).
2. Now gcd(a,b) == 1
3. Find solution to aU + bV = 1 using Extended Euclidean algorithm
4. Multiply equation by c. Now you have a(Uc) + b (Vc) = c
5. You found solution x = U*c and y = V * c