gaucho_josecito's blog

By gaucho_josecito, history, 6 years ago, In English

Hi.

So I took part in yesterday's contest and I realized that for problem E, instead of considering the ball bouncing on the walls, we can just imagine there are infinite rectangles on the plane, one next to the other, and the ball will continue forever in the initial direction. We need to find if at any given time, x will be a multiple of n and y will be a multiple of m. This problem is analogous to the original one.

So we need to find a number k such that n|(x + vx * k) and m|(y + vy * k). This is similar to "find the first number that satisfies a given remainder modulo n and a given remainder modulo m". That's where I got stuck. I thought about Chinese Remainder Theorem, but since numbers are not necessarily coprime, it wouldn't work. I also thought about something in the terms of Euclidean algorithm, but I couldn't come up with anything either.

So, how can I solve that problem: find the first number that satisfies a given a remainder modulo n and a given remainder modulo m.

Thanks in advance!

Full text and comments »

  • Vote: I like it
  • +29
  • Vote: I do not like it