I want to compute the sum $$$\left\lfloor \frac{m}{n} \right\rfloor + \left\lfloor \frac{2m}{n} \right\rfloor + \cdots + \left\lfloor \frac{(n-1)m}{n} \right\rfloor = \sum_{k=1}^{n-1} \left\lfloor \frac{km}{n} \right\rfloor$$$ in log time.

I know that when $$$\gcd(m,n) = 1,$$$ this can be viewed as counting lattice points under the line $$$y=\frac{m}{n} x$$$ and by symmetry it's equal to half the number of lattice points contained in the entire rectangle (because there's no points exactly on the line segment as $$$\gcd(m,n) = 1$$$), so the sum is equal to $$$\frac{(m-1)(n-1)}{2}.$$$ (When $$$m,n$$$ are prime, the sum is a nice lemma that is used in a proof of Quadratic Reciprocity.)

I'm told that there's a way to think about this that is similar to the Euclidean Algorithm for gcd. Is there a connection to that? Is there a way to generalize the lattice point counting approach for relatively prime $$$m,n$$$?