### dtalamas24's blog

By dtalamas24, 8 years ago,

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

 » 8 years ago, # |   +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!
•  » » 8 years ago, # ^ | ← 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 ?
•  » » » 8 years ago, # ^ |   +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.
 » 8 years ago, # | ← 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.
 » 6 years ago, # |   +7 Can You share the link to the original problem,please?