Author: Nitesh Singh
Tester: Nitesh Singh
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
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.
|multiples of 9||remainder with 7||Numbers not possible to Generate|
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