# Finding sum of all integral parts

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?

-
Why is it $O(M)$? If $N=M$, the sum is $M(M-1)/2$, which is $O(M^2)$. – user1551 Mar 9 '13 at 8:23
Is there any special relationship between M and N? For example, if M and N are coprime, I believe the calculation could be done in O(1) time. – Mike Mar 9 '13 at 8:36
I edited... It was sum to calculated in O(M) – Shashwat Kumar Mar 9 '13 at 8:37
I got the solution. It is O(log n*log m). sum = (NM - N - M + gcd(N, M))/2) – Shashwat Kumar Mar 9 '13 at 8:38
@Shashwat If you have an answer, write it down. wait for comment for a while and then accept it yourself. – achille hui Mar 9 '13 at 8:51

$$\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.