### 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. math, gcd, Comments (5)
 » 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 →   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 ?
•  » » » 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 →   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.