Let $M,N,c$ be positive integer. It was astonishing when trying to solve $\sum_{k=0}^N\sum_{l=0}^M\left\lfloor\frac{k+l}{c}\right\rfloor$ to obtain this rather complex looking result
\begin{align*}
\color{blue}{\sum_{k=0}^N}&\color{blue}{\sum_{l=0}^M\left\lfloor\frac{k+l}{c}\right\rfloor}\tag{1}\\
&=-\frac{1}{2}c(1-c)\left\lfloor\frac{M}{c}\right\rfloor\left\lfloor\frac{N}{c}\right\rfloor\left\lfloor\frac{2c-2}{c}\right\rfloor\\
&\quad+\frac{1}{2}m(m+1)\left\lfloor\frac{N}{c}\right\rfloor\left\lfloor\frac{c+m-1}{c}\right\rfloor
+\frac{1}{2}n(n+1)\left\lfloor\frac{M}{c}\right\rfloor\left\lfloor\frac{c+n-1}{c}\right\rfloor\\
&\quad+\left(m+1-\frac{c}{2}\right)(n+1)\left\lfloor\frac{M}{c}\right\rfloor+\left(n+1-\frac{c}{2}\right)(m+1)\left\lfloor\frac{N}{c}\right\rfloor\\
&\quad+\frac{1}{2}(n+1)c\left\lfloor\frac{M}{c}\right\rfloor^2+\frac{1}{2}(m+1)c\left\lfloor\frac{N}{c}\right\rfloor^2\\
&\quad+c(m+n+2-c)\left\lfloor\frac{M}{c}\right\rfloor\left\lfloor\frac{N}{c}\right\rfloor\\
&\quad+\frac{1}{2}c^2\left\lfloor\frac{M}{c}\right\rfloor\left\lfloor\frac{M}{c}\right\rfloor
\left(\left\lfloor\frac{M}{c}\right\rfloor+\left\lfloor\frac{N}{c}\right\rfloor\right)\\
&\quad+\left(\frac{1}{2}((m+n)^2+3(m+n)+2)-\left(m+n+\frac{3}{2}\right)c+\frac{1}{2}c^2\right)\left\lfloor\frac{m+n}{c}\right\rfloor
\end{align*}
Moreover what really baffled me was the long and cumbersome road to find this identity. In fact I needed to derive closed formulas for the three sums ($n,a,c$ integer $n\geq 0, c>0, 0\leq a <c$):
\begin{align*}
&\sum_{k=0}^n\left\lfloor\frac{k+a}{c}\right\rfloor,\qquad\sum_{k=0}^n k\left\lfloor \frac{k+a}{c}\right\rfloor,\qquad\sum_{k=0}^n\left\lfloor\frac{k+a}{c}\right\rfloor^2\\
\end{align*}
and used these intermediate results to calculate (1) with tedious, lengthy calculations. You might have a look at this answer to see some steps.
Question: Do we have some other, maybe more advanced techniques to tackle (1) more efficiently than I did in the referred answer?
Best Answer
Let $$S_n=\sum_{k=0}^{n-1}\left\lfloor \frac kc\right\rfloor$$ and $$ T_n=\sum_{k=0}^{n-1}S_k.$$ Then we are looking for $$ \begin{align}\sum_{k=0}^N\sum_{l=0}^M\left\lfloor\frac{k+l}{c}\right\rfloor &=\sum_{k=0}^N(S_{M+k+1}-S_k)\\ &=T_{N+M+2}-T_{M+1}-T_{N+1}\end{align}$$ Note that for $n=qc+r$ with $0\le r<c$, we have $$S_n=c\sum_{k=0}^{q-1}k+rq=\frac c2{q(q-1)}+rq.$$ By the same trick, $$\begin{align}T_n&=\sum_{k=0}^{q-1}\left(\frac c2{k(k-1)}+\frac{k(k-1)}2k\right)+r\cdot\frac c2{q(q-1)} +\frac{r(r-1)}2q\\ &=\frac {cq(q-1)(q-2)}6+\frac{q(q-1)(q-2)(3q-1)}{12}+\frac{rq(cq-c+r-1)}2\end{align}$$