Given a point $(a,b)$ with positive coordinates, I'd like to count the number of lattice points $(x,y)$ with the same parity (i.e., $x \equiv y \ (mod \ 2)$) inside the triangle $(0,0)(a,0)(a,b)$. How to compute it fast?
Note that without the parity requirement, it can be done using Pick's theorem directly.
After some trials, I come up with a solution similar to the Euclidean algorithm.
We want to calculate $\sum_{0 \leq x \leq a}\lfloor \frac{\frac{b}{a}x+(x\%2)}{2} \rfloor$ where $\%$ means the standard modulo operator. We separate into two parts: $x$ is odd and $x$ is even. For the first case, we write as $\sum_{0 \leq 2t+1 \leq a}\lfloor \frac{2bt+a+b}{2a} \rfloor$; for the second case, we write as $\sum_{0 \leq 2t \leq a}\lfloor \frac{bt}{a} \rfloor$. Therefore, it is suffice to compute $f(a,b,c,n)=\sum_{0 \leq x \leq n}\lfloor\frac{ax+b}{c} \rfloor$ fast.
If $a \geq c$ or $b \geq c$, we can write $a=q_1 c+r_1$ and $b=q_2 c+r_2$ where $r_1$ and $r_2$ are remainders. Hence, $f(a,b,c,n)=\sum_{0 \leq x \leq n}\lfloor q_1 x + q_2 + \frac{r_{1}x + r_{2}}{c} \rfloor=(\sum_{0 \leq x \leq n}q_1 x + q_2) +\sum_{0 \leq x \leq n}\lfloor \frac{r_1 x + r_2}{c} \rfloor$. The first part can be calculated directly, so we just need to consider the case $a \lt c$ and $b \lt c$.
In this case, it turns out that $f(a,b,c,n)=\sum_{0 \leq x \leq n}\lfloor\frac{ax+b}{c} \rfloor=\sum_{0 \leq x \leq n}\sum_{0 \leq j \leq \lfloor\frac{ax+b}{c} \rfloor-1}1=\sum_{0 \leq j \leq \lfloor\frac{an+b}{c} \rfloor-1}\sum_{0 \leq x \leq n}[j<\lfloor\frac{ax+b}{c} \rfloor]=\sum_{0 \leq j \leq \lfloor\frac{an+b}{c} \rfloor-1}\sum_{0 \leq x \leq n}[cj<ax+b-c+1]=\sum_{0 \leq j \leq \lfloor\frac{an+b}{c} \rfloor-1}(n-\lfloor\frac{cj+c-b-1}{a} \rfloor)=n\lfloor\frac{an+b}{c} \rfloor-\sum_{0 \leq j \leq \lfloor\frac{an+b}{c} \rfloor-1}\lfloor\frac{cj+c-b-1}{a} \rfloor=n\lfloor\frac{an+b}{c} \rfloor-f(c,c-b-1,a,\lfloor\frac{an+b}{c} \rfloor-1)$.
The above runs similar to the Euclidean algorithm, and we solve the problem in $O(log(max(a,b)))$.
