Блог пользователя allthecode

Small Math Question
Автор allthecode, 12 лет назад, По-английски

Hi,

If you are located at the bottom left corner (0, 0) of a plain with H x W cells, and you move U positions up and R positions right in each step, how to calculate if you will eventually arrive to a specific cell after any amount of steps? (If you fall to the right of the plane, you get to the left of the plane. Same with falling up)

Thanks.

  • Проголосовать: нравится
  • -13
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

You must find an integer k that satisfies: (k*r)%w=x & (k*u)%h=y. If (w*h)<=10^8 you can simply try all k: 1<=k<=lcm(w,h). Or you can solve system of two Diofant's equations: k*r=a*w+x & k*u=b*h+y. Just use extended Euclid algo. Good luck!

→ Ответить
  • »
    »
    12 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    But the extended euclid algorithm solves for x and y in ax + by = gcd(a, b), where is the gcd part in k*r=a*w+x & k*u=b*h+y ?

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

      First, let's solve Diofant equation with two variables: a*x+b*y=c. It's obvious that linear combination of a and b must be divisible by their GCD. So, if c is not divisible by their GCD => there is no solution. We can try to find a solution in a such form: x=x1*(c/d) & y=y1*(c/d), where d=GCD(a,b). Our equality can be rewriten as: a*x1*(c/d)+b*y1*(c/d)=c => a*x1+b*y1=d, which can be solved by the extended Euclid algo, as you know. x1 and y1 are the initial values, general solution can be obtained in a such way: x(n)=x1+n*(b/d) & y(n)=y1-n*(a/d), n — any integer. So, we can solve both equations of our system and then intersect solutions like two modular equations. Also I recommend you to read about CRT — it is a general method of solving systems of modular equations.

      → Ответить
»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

You can answer that question in O(1). For each step when you go up y coordinate increases with U and for each step you go right x coordinate increases with R. Because you start walking from (0,0) you can go to every cell with coordinates (X,Y) if and only if X%R = 0 and Y%U=0 and X/R = Y/U.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Can You share the link to the original problem,please?

→ Ответить