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.
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).
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
1 2 4 5 1
10 12 3 9 16
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)
Thanks in advance.