I managed to find an efficient algorithm (polynomial time in $P$,$Q$ and $N$) for the following sum:

$$\sum_{i=0}^{N} \lfloor iP/Q \rfloor,$$ where $P,Q$ are relatively prime positive integers. When $N=Q-1$ it's fairly easy to get a simple closed form, and this is also well-known. The details of the general algorithm can be found here http://mathforum.org/library/drmath/view/73120.html. It is a very nice algorithm that resembles the standard GCD algorithm somewhat.

I'm trying to generalize this algorithm to sums of the following form: $$\sum_{i=0}^{N} (i^{k0}) \cdot (\lfloor (iP/Q) \rfloor)^{k1},$$ where $k_0$, and $k_{1}$ are non-negative integers. Does anyone have any good ideas for this? The algorithm doesn't have to be polynomial in $k_{0}$ and $k_{1}$, and algorithms for small values of $k_{0}$ and $k_{1}$ would also be interesting (such as $k_{0} = 0$). Obviously, $k_{1} = 0$ is not interesting.