Internet Problem Solving Contest

IPSC 2005

Solution to Problem G – Gears In Action

First we realize that odd gears rotate clockwise and even gears rotate counter-clockwise. If i is odd we change the bi value: bi :=(ai-bi) mod ai. From now we can assume that every gear rotates clockwise at the speed 1 tooth per second.

Let x be the first time when first two gears are in states b1 and b2 respectively. Then x=a1*n1+b1= a2*n2 +b2. The value n1 is the number of turns of the first gear. We know the values a1, b1, a2, b2 and we want to find such n1 and n2 that: a1*n1-a2*n2= b2-b1
Let d:=GCD(a1, a2), GCD stands for greatest common divisor. If b2-b1 is not divisible by d then the solution doesn't exist. Else we find such n1 and n2 that a1*n1- a2*n2=d. These numbers can be found using the extended Euclidean algorithm.

Now let l:=(b2-b1)/d. Then a1*l*n1- a2*l*n2= b2-b1 is a solution, but not necessary the best. Let h:=LCM(a1, a2) -- this is the first nonzero time when the states of both gears are 0 (LCM is least common multiple). So this is the period of the movement of the two gears. Therefore a1*l* n1- a2*l* n2 +k*h-k*h =a1*(l*n1+ k*h/a1)- a2* (l*n2+k*h/a2) is also a solution.

But we want to find the smallest time when gears meet, so l*n1+k*h/a1 should be as small as possible. Let m1:=l*n1+ k*h/a1 and a1*m1+ b1 is the first time when gears meet. We know that a1*m1+ b1 is less than h= LCM(a1, a2) and the gears met only once until time h. Clearly m1 is nonnegative and less than h/1, so m1 :=(l*n1) mod (h/a1).

The first two gears meet at LCM(a1, a2)*n + a1* m1+ b1 for every nonnegative integer n. The third gear has to satisfy equation x=a3*n3+ b3=LCM(a1, a2)*n + a1* m1+ b1. We can use the same algorithm to find minimum n and n3 as before.

So after we have find the time when first k gears meet we can find the time when first k+1 gears meet. For the first k gears the time is a*n+b and for the k+1-th gear the time is ak+1*nk+1+bk+1. We can use the same algorithm as before to find minimal n and nk+1. So complexity of our algorithm is O(N*M), because for each gear we calculate some numbers. Euclidean algorithm works in O(M) where M is number of digits of numbers.