COPR16G: Editorial

PROBLEM LINK:

Practice

Contest

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.

7 Likes

Well this problem does not have to do anything with problem solving. It’s just a mathematical “have-to-know” theorem or I would rather say a trick. Most of the people in this community do not have this kind of mathematical knowledge and for those who have, are generally IMO aspirants.

If you really think that this problem should be put out, try explaining the proof of “Chicken McNugget Theorem”…

9 Likes

There is a small mistake in the explanation.
Quoting the explanation - We can also see the above problem as finding the largest integer which can be expressed as ax + by for some integers, x and y.

Actually the correct replacement of the content highlighted is - finding the largest integer which cannot be expressed as ax + by.

1 Like

Actually, one can arrive at the solution without knowing the theorem in advance. Just basic number theory intuition. Also, there’s indeed a typo as pointed out by @santhosh3.

2 Likes

Why did you have to put “The easiest problem of the lot !” :sob:
confidence gir jaata hai is’se bas.

4 Likes