Hello everyone,

I have such problem: there are 2 elevators which go only upwards, and stop on only particular floors, each elevator is described by 2 numbers: a,r where a is a number of floor on which the elevator starts and r is a number which is a period of elevator's stops. For example, if we have elevator a=1, r=3 then it stops on that floors: 1,4,7,10,13,16,19 and so on and so forth. And now my question: how to find the first common floor of those 2 elevators and the period of repeating common floors. I know that two elevators have common floor when GCD(r1,r2)|p where p is |a1-a2| so it should be something like that:

a1+x*r1 = a2+y*r2

x*r1 + (-y)*r2 = a2 - a1

I don't know what to do know and if it is a good way of solving that problem, I though about The Extended Euclidean Algorithm which says:

ax+by=gcd(a,b)

So we could try to do something like that:

(a2-a1)/gcd(r1,r2)=k

a2-a1=gcd(r1,r2)*k

x*r1 + (-y)*r2 = gcd(r1,r2)*k

But... afair a,b in extended euclidean algorithm must be integers so we can't divide it by k.

Doest anyone know how to solve it ?

Regards,

apacz