Internet Problem Solving Contest

• Correct output – G1
• Correct output – G2
• C++ code that solves both data sets

First we realize that odd gears rotate clockwise and even gears rotate counter-clockwise. If i is odd we change the b_i value: b_i :=(a_i-b_i) mod a_i. 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 b₁ and b₂ respectively. Then x=a₁*n₁+b₁= a₂*n₂ +b₂. The value n₁ is the number of turns of the first gear. We know the values a₁, b₁, a₂, b₂ and we want to find such n₁ and n₂ that: a₁*n₁-a₂*n₂= b₂-b₁
Let d:=GCD(a₁, a₂), GCD stands for greatest common divisor. If b₂-b₁ is not divisible by d then the solution doesn't exist. Else we find such n₁ and n₂ that a₁*n₁- a₂*n₂=d. These numbers can be found using the extended Euclidean algorithm.

Now let l:=(b₂-b₁)/d. Then a₁*l*n₁- a₂*l*n₂= b₂-b₁ is a solution, but not necessary the best. Let h:=LCM(a₁, a₂) -- 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 a₁*l* n₁- a₂*l* n₂ +k*h-k*h =a₁*(l*n₁+ k*h/a₁)- a₂* (l*n₂+k*h/a₂) is also a solution.

But we want to find the smallest time when gears meet, so l*n₁+k*h/a₁ should be as small as possible. Let m₁:=l*n₁+ k*h/a₁ and a₁*m₁+ b₁ is the first time when gears meet. We know that a₁*m₁+ b₁ is less than h= LCM(a₁, a₂) and the gears met only once until time h. Clearly m₁ is nonnegative and less than h/₁, so m₁ :=(l*n₁) mod (h/a₁).

The first two gears meet at LCM(a₁, a₂)*n + a₁* m₁+ b₁ for every nonnegative integer n. The third gear has to satisfy equation x=a₃*n₃+ b₃=LCM(a₁, a₂)*n + a₁* m₁+ b₁. We can use the same algorithm to find minimum n and n₃ 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 a_k+1*n_k+1+b_k+1. We can use the same algorithm as before to find minimal n and n_k+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.