Finding sum of all integral parts

Question

Given two numbers $M$ and $N$, Let $q_i$ be the integer part of $\frac{iN}{M}$. What is $$ \sum_{i=0}^{M-1} q_i? $$ The Sum is obviously can be calculated in $O(M)$. Can this be done in less time, maybe $O(1)$ if there exists some simpler reduced expression?

Answer 1

Assuming M and N are integers, I believe your formula can be rewritten as

$$\sum\limits_{i=0}^{M-1}\frac{iN}M-\frac1M\sum\limits_{i=0}^{M-1}iN \mod M.$$

The first sum is an arithmetic sum. There is a formula for arithmetic sums that can be done in O(1) time. The second summation is the sum of remainders from the division. If $N$ and $M$ are coprime, no 2 of these remainders are the same, reducing the sum to $\sum\limits_{i=0}^{M-1}i$, which is another arithmetic sum.

I'm sure the formula can be adjusted in the case where $M$ and $N$ are not coprime. Maybe someone else can fill in the blanks while I'm getting some sleep, assuming you're interested. My guess is if you know nothing about M and N, your computation time will stem from performing the Euclidean algorithm to obtain a gcd, which I believe should be less than linear time.