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_{1} and
b_{2} respectively. Then x=a_{1}*n_{1}+b_{1}=
a_{2}*n_{2} +b_{2}. The value n_{1} is the
number of turns of the first gear. We know the values a_{1},
b_{1}, a_{2}, b_{2} and we want to find such
n_{1} and n_{2} that:
a_{1}*n_{1}-a_{2}*n_{2}=
b_{2}-b_{1}

Let d:=GCD(a_{1}, a_{2}),
GCD stands for greatest common divisor. If b_{2}-b_{1} is not
divisible by d then the solution doesn't exist. Else we find such
n_{1} and n_{2} that a_{1}*n_{1}-
a_{2}*n_{2}=d. These numbers can be found using the extended
Euclidean algorithm.

Now let l:=(b_{2}-b_{1})/d. Then
a_{1}*l*n_{1}- a_{2}*l*n_{2}=
b_{2}-b_{1} is a solution, but not necessary the best. Let
h:=LCM(a_{1}, a_{2}) -- 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_{1}*l*
n_{1}- a_{2}*l* n_{2} +k*h-k*h
=a_{1}*(l*n_{1}+ k*h/a_{1})- a_{2}*
(l*n_{2}+k*h/a_{2}) is also a solution.

But we want to find the smallest time when gears meet, so
l*n_{1}+k*h/a_{1} should be as small as possible. Let
m_{1}:=l*n_{1}+ k*h/a_{1} and
a_{1}*m_{1}+ b_{1} is the first time when gears meet.
We know that a_{1}*m_{1}+ b_{1} is less than h=
LCM(a_{1}, a_{2}) and the gears met only once until time h.
Clearly m_{1} is nonnegative and less than h/_{1}, so
m_{1} :=(l*n_{1}) mod (h/a_{1}).

The first two gears meet at LCM(a_{1}, a_{2})*n +
a_{1}* m_{1}+ b_{1} for every nonnegative integer n.
The third gear has to satisfy equation x=a_{3}*n_{3}+
b_{3}=LCM(a_{1}, a_{2})*n + a_{1}*
m_{1}+ b_{1}. We can use the same algorithm to find minimum n
and n_{3} 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.