Let’s go in reverse order, from (targetX, targetY) to (1, 1). So, now we can move from (x, y) to (x+y, y), (x, y+x), (x/2, y) if x is even, and (x, y/2) if y is even.

When is it optimal to use the third and fourth operations?

Think how GCD of (x, y) is affected if we apply the first two operations.

How can we check if we can reach (1, 1) using the GCD value calculate above?