PROBLEM LINK:
Author: Nitesh Singh
Tester: Nitesh Singh
DIFFICULTY:
EASY-MEDIUM, MATHS
PREREQUISITES:
Coprime,multiplication,Logic
PROBLEM:
given positive integers
x1, x2, . . . , xn with gcd(x1, x2, . . . , xn) = 1, compute the largest
integer not representable as a non-negative integer linear
combination of the xi
.
This largest integer is sometimes denoted g(x1, . . . , xn).
The restriction gcd(x1, x2, . . . , xn) = 1 is necessary for the
definition to be meaningful, for otherwise every non-negative
integer linear combination is divisible by this gcd in that case answer would be infinity
EXPLANATION:
Given 2 numbers ‘a’ and ‘b’ there equation is ax+by,a and b are coprime
So all number can be generate just plot ax+by=N find a and and but the condition here was that a and b cannot be negative,in that case only will there be a maximum number that cannot be generated.
consider 7,9
7x+9y=k
x=(k-9y)/7
| multiples of 9 | remainder with 7 | Numbers not possible to Generate |
|---|---|---|
| 9 | 2 | 2 |
| 18 | 4 | 4,4+7=11 |
| 27 | 6 | 6,6+7=13,20 |
| 36 | 1 | 1,8,15,22,29 |
| 45 | 3 | 3,10,17,24,31,38 |
| 54 | 5 | 5,12,19,26,33,40,47 |
In the above table we see that with multiples of 9 we have generated all possible remainders of 7.
so x=(k-9y)/7 here x can always be intere for any value of k because whatever value of k we take it will give a remainder 0 to 6 and we will put y accordingly to compensate that remainder like k=101 k%7=3 so put y=5
x=(101-9*5)/7 =8