Problem - 2 elevators, when do they meet ?

[apacz]

Hi, I have such problem: there is 2 elevators in a one building of x floors, they drive only upwards. And we have such data (for example):
1. elevator:
a1=1
r=3
2. elevator
a1=2
r=4

a1 is a numer of the floor from which each elevator starts and r is a period of an elevator breaks - for example, second elevator starts on the 2nd floor, then it stops on the 6h, 10th, 14th and so on and so forth. And here is my question, how to calculate the lowest number of the floor on which two elevators meets and what the period would be? I know that they will meet when GCD(r_1,r_2)|p where p is |a1_1 - a1_2|.
Regards,
apacz

[quzah]

I'm not quite sure why you're posting your homework on the contests board... Consider this your lucky day.

for( e1 = start1, e2 = start2; e1 != e2; )
{
    while( e1 < e2 )
        e1 += increment1;
    while( e2 < e1 )
        e2 += increment2;
}

Yeah, that looks about right.


Quzah.