### PROBLEM LINK:

**Author:** Bhuvnesh Jain

**Tester:** Bhuvnesh Jain

**Editorialist:** Bhuvnesh Jain

### DIFFICULTY:

EASY

### PREREQUISITES:

Diophantine Equations, GCD

### PROBLEM:

You are provided with coins of denominations **a** and **b**.

You are required to find the least value of n, such that all currency values greater than or equal to n can be made using any number of coins of denomination **a** and **b** and in any order. If no such number exists, print **-1** in that case.

### EXPLANATION:

Let us first write the statement as mathematical equations and then procede furthur.

*ax + by = n, where x and y are integers.*

and *au + bv = n+1, where u and v are integers.*

The above equations hold **for all integers >= n, if solution exists**. Let us subtract the 2 equations. We get,

*ar + bs = 1, where r and s are integers.*

Hence we can easily see that solutions exists **iff gcd(a, b)==1**. (Using the condition for solvability of linear Diophantine equation).

Now we need to find the value of least possible **n**. We can also see the above problem as finding the largest interger which can be expressed as **ax + by** for some integers, x and y. A simple google search could have helped you, hence the name “GET AC IN ONE GO”. The answer is simply **(a.b - a - b)**. You can see a detailed proof here.

Hence, the solution is **(a.b - a - b + 1)**, when **gcd(a, b) = 1** else **-1**.

### COMPLEXITY

O(log(max(a, b))) per test case

### AUTHOR’S SOLUTION:

Author’s solution can be found here.