20q ≤ 50p ≤ 21q
The LHS inequality is shown as line 0A and RHS as line 0B in the following graph...
#intersections in shaded area 0AB (including all grid intersections that occur ON the outer lines - subsequently referred to as "outers")
= 0AC
(with all outers) + ABDC
(with all outers except AC) - 0BD
(with all outers except 0B)
To calculate the number of grid intersection points within triangle 0AC, turn the triangle into rectangle 0EAC, subtract the number of intersections that occur on the diagonal 0A, and then divide by two, and finally add back the number of diagonal intersection points. For this to work, the outer edges of the rectangle must align with the grid intersection points. Therefore increase the range of q to 0≤q≤100 (which yields integer coordinates for A,B,C and D), and then at the end subtract the results for q=0 and q=100 to obtain the desired range of 1≤q≤99
At point E q=100
At points A and C, p=100*20/50 = 40
At points B and D, p=100*21/50 = 42
OAC (with all outers)
The number of grid point intersections on line 0A is Ia=21. The first few are (0,0) (2,5) (4,10) (6,15)...(40,100) therefore the total number is (100/5)+1
Number of intersections within OAC is ((40+1)*(100+1) - Ia )/2 + Ia = 2081
ABDC (with all outers except AC)
(42-40) * (100+1) = 202
OBD (with all outers except on line 0B)
The number of grid point intersections on line 0A is Ib=3. These are (0,0) (21,50) (42,100)
Number of intersections within ODB is ((42+1)*(100+1) - Ib)/2 = 2170
INTERIM RESULT
0AC + ABDC - 0BD
= 2081 + 202 - 2170
= 113
FINAL RESULT
Remove intersections for q=0, and q=100. When q=0 we have 0 ≤ p ≤ 0 therefore one option at (0,0)
and when q=100 we have 40 ≤ p≤ 42 therefore 3 options at (40,100) (41,100) (42,100)
Removing these gives number of (p,q)
= 113 - (1+3)
=
109