- #1
apacz
- 1
- 0
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 (first elevator (a1,r1), second elevator (a2,r2) ) 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 ? Maybe there is some other way to solve it?
Regards,
apacz
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 (first elevator (a1,r1), second elevator (a2,r2) ) 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 ? Maybe there is some other way to solve it?
Regards,
apacz