0
$\begingroup$

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.

1 Answers 1

1

Hint $\rm\ A\:\mathbb Z + B\:\mathbb Z = \gcd(A,B)\:\mathbb Z,\ \ C\:\mathbb Z + D\: \mathbb Z = \gcd(C,D)\:\mathbb Z.\:$ An integer is in both of these sets iff it is divisible by both $\rm\:\gcd(A,B)\:$ and $\rm\:\gcd(C,D)\:$ iff it is divisible by their LCM.

For example, consider the third test case: $\rm\:A,B,C,D,K = 10,12,3,9,16.\:$ We have $\rm\:gcd(10,12) = 2,\:$ and $\rm\:\gcd(3,9)=3,\:$ and $\rm\:lcm(2,3) = 6,\:$ so their are $\rm\:\lfloor 16/6\rfloor = 2\:$ positive integers $\le 16$ divisible by both $2,3,\:$ and $2$ negative integers $\ge -16,\:$ so, with $0$, there are $5$ total in the interval $[-16,16].$

  • 0
    @BillDubuque Thanks for the advice.2012-04-02