## 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