### PROBLEM LINK:

**Author:** Jatin Gupta & Gaurav Aggarwal

**Tester:** Aanya Jindal

**Editorialist:** Aanya Jindal

### DIFFICULTY:

Easy-medium

### PREREQUISITES

GCD, math

### PROBLEM:

Given start and end positions on a line and the number of steps in forward and backward direction Adhiraj can take, find if the end position can be reached under the constraints.

### QUICK EXPLANATION:

ax + by = c has a solution for x and y if and only if c is a multiple of gcd of a and b.

(Linear Diophantine Equation).

In our problem a = f, b = b and c = y-x. So after checking all boundary conditions if gcd of f and b divides the distance to be travelled, then Adhiraj can reach his destination.

### EXPLANATION:

The problem required handling corner cases as well along with the knowledge of the gcd which will be used for main solution.

Following cases should be handled properly:

CASE 1: When c = y-x = 0

Answer will always be **YES** because Adhiraj has no steps to move.

In further cases we assume that c != 0

CASE 2: When f = 0 AND b = 0

Answer will always be **NO** because Adhiraj can’t make any step at all and thus won’t be able to reach his destination.

CASE 3: When f = 0 AND b != 0

Here Adhiraj can only move in backward direction and that too only in multiples of b.

Thus,

If c < 0 AND c%b == 0 answer will be YES

Else answer will be NO

CASE 4: When f != 0 AND b == 0

By similar reasoning as CASE 3,

If c > 0 AND c%f == 0 answer will be YES

Else answer will be NO

CASE 5: When none of the above cases follow, i.e. f, b, c != 0

When we try to solve this case, we end up with the equation,

fx - by = c,

Where, x is the number of steps in forward direction

y is the number of steps in backward direction.

It should however be noted that x and y should only take positive integer values.

(since, steps can’t be negative)

This equation is indeed a Linear Diophantine Equation and its solution says that

ax + by = c has integral solutions for x and y if and only if c is a multiple of gcd of a and b.

Let’s see this intuitively using an example,

Suppose that f = 4 and b = 6. So we can easily see that to travel 2 in +X, we can take 2 steps forward and 1 step backward. So, ‘ffb’ gives +2. Now, to travel 2 in -X, we can take 1 step backward and 1 step forward. So, ‘bf’ gives -2. Now we can travel in multiples of 2. But see if you can take steps such that distance travelled is not a multiple of 2 (which is GCD of 4 and 6).

Thus,

If c%gcd(f, b) == 0 answer will be YES

Else answer will be NO

To compute gcd, in-built function __gcd can be used or any implementation of eucledian gcd will work.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.