• + 2 comments

    administrator, please remove the spamming (totally unrelated) messages in this forum, now back to the problem the solution lies in realizing that GCD(a,b) == GCD(a+n*b, b+m*a) == GCD(x,y)

    Happy coding!

    • + 2 comments

      Can you please elaborate this further? How did you think and reason about it yourself in the first place?

      Thanks in advance.

      • + 1 comment
        1. Point (a,b) is the start
        2. According to the problem, from (a,b) he can go, east: (a+b, b), north: (a, a+b), west: (a-b, b), south: (a, b-a) in this 2D grid
        3. From (2) we can infer that any destination point will be of the form (a+n*b, b+m*a)
        4. Mathematical property: adding or subtracting a multiple of one number to another does not change their greatest common divisor (GCD) e.g. GCD(12, 8) = 4 = GCD(12+8*1, 8+12*2) = GCD(20, 32) = 4
        5. With that in mind, given another point (x,y), we can infer that if we can reach that point, then it might be of the form (a+n*b, b+m*a) hence their GCD must be the same if (x,y) is reachable from (a, b)

        6. GCD function is function gcd(a,b) { return (a % b == 0) ? b : gcd(b, a % b); }

        Hope that helps!