# Codathon Editorial

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
so the biggest not not possible to generate: ***`a*(b-1)+b*-1=a*b-a-b`***

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

## AUTHOR’S AND TESTER’S SOLUTIONS:

Solution :c++ Python