If $a$, $b$, and $c$ are known, and $x$ and $y$ are integers greater than or equal to zero, how many possible values of ($x$, $y$) exist that satisfy the equation $$ax + by \le c\,?$$
I have worked it out to equal the following:
$$\left(\sum_{n=0}^{\lfloor c/a \rfloor}\left\lfloor\frac{c - an}{b}\right\rfloor\right)+\left\lfloor\frac{c}{a}\right\rfloor+1$$
I am trying to solve this as a coding problem, and at the moment this requires a loop:
int sum = 0;
int nMax = c/a;
for(int n = 0; n <= nMax; ++n)
sum += (c-a*n)/b;
sum += nMax + 1;
It would be faster if I could figure out how to take away this loop.
I attempted another simplification step, with the following (incorrect) formula:
$$\left\lfloor\frac{\sum_{n=0}^{\lfloor c/a \rfloor}(c-an)}{b}\right\rfloor + \left\lfloor\frac{c}{a}\right\rfloor + 1$$
My understanding is that this is incorrect because the floor function is not linear:
$$\sum_{n=0}^c\left\lfloor\frac{n}{m}\right\rfloor \ne \left\lfloor \frac{\sum_{n=0}^{c}n}{m}\right\rfloor$$
I'm stuck now. Is there another way to solve the problem, which doesn't involve such a large loop?
It occurs to be that you could express this as a line:
$$ax + by \le c$$ $$y \le \frac{c}{b} - \left(\frac{a}{b}\right)x$$
So the problem can now be expressed as:
How many lattice points are on or below the line $$y = \frac{c}{b} - \left(\frac{a}{b}\right)x$$