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.