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.They will be my answer for this problem.
I tried using the same technique in my C++ code but it's not working.
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/
Thanks in advance.