Problem: We have N questions in a question paper. Each correct answer would mean +a marks and wrong answer would mean -b marks. Leaving a question unattended would give a 0 marks. Tell how many different total marks are possible in terms of N ,a,b.
E.g.: N=1 ,a=4 , b=3
ans–>3
N=2, a=1, b=1
ans–>5
Edit-problem link
Problem link?
what are the constraints on N,a,b?
please check the edit i made
An equivalent formation of the question is: How many different values can ax-by take such that x, y \ge 0 and x+y \le n.
Maximum value of this is a\cdot N - b \cdot 0 \le 10^6 and minimum value is a\cdot 0 - b \cdot N \ge -10^6, so we can just iterate through each value and check if it is possible.
We check if a number r is possible as follows.
Let d = \gcd(a,b). We know, if r is possible, d must divide r. Using to Bezout’s identity, there exist x_0, y_0 such that ax_0-by_0 = d. We can multiple both sides by \frac{r}{d} to get a solution ax_1 - by_1 = r. All other solutions to ax - by = r are given by (x,y) = \left(x_1 + k\frac{b}{d}, y_1 + k\frac{a}{d} \right) where k is an integer. If we can find a k such that x\ge 0, y\ge 0, x+y \le N, r is possible. There is a range of k for each of these 3 inequalities, we just check if the intersection of these ranges is non empty.
Thank You very much for this awesome solution!