Number of grid points inside a triangle

Question

I need to find a number of integer points inside a triangle with vertices $(0,0)$, $(A,0)$ and $(0,B)$, where $A$ and $B$ are positive integers. This problem can be reduced to the following Diophantine inequality (assuming $x \gt 0, y \gt 0$):

$$Bx + Ay < AB$$

I can find a number of positive solutions of this inequality by a simple $O(A + B)$ algorithm, however I suspect there should be a faster method, may be (ideally) a closed formula.

Any ideas?

Answer 1

The given problem (1) is basically equivalent to (2) finding how many integer points lie on the segment connecting (0,A) and (B,0), because if you know that the rest is trivial (Why? Because you know how many integer points lie in the rectangle (0,0), (A,0), (0,B), (A,B)). The problem (2) doesn't seem too difficult either as this line/segment (the rectangle's diagonal) has an algebraic equation and one can deduce how many integer points satisfy that equation.

In fact a point lies on the segment iff it has the form:
(k.A, k.B) where k is some real number in [0,1].

Now think what k should be for both k.A and k.B to be integers.
Hint: the answer has something to do with the divisors of A and B.