Nuu's blog

Number of steps to coincide the position on two circles [HELP]
By Nuu, history, 7 years ago, In English

Hi guys, Today i sees a apparently easy math problem (but i can't solved):

Two persons walk simutanious around two circles with size A and B with positions [1,2,3,...,A] and [1,2,3,...,B].

Then follow Q querys. Each query give two positions x and y, and asks the number of step for person A arrive on position x and person B arrive on position y (on same time) using O(1).

Thanks guys, i'm very novice in math problems.

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

It asks for a question like k mod A = x and k mod B = y. This is Chinese remainder theorem application.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Dear Nuu,

The equivalent Chinese Remainder problem is: Find the smallest positive integer 0 <= n <= A*B - 1 such that n mod A = x - 1 and n mod B = y - 1.

Best wishes,

→ Reply