IMC 2013 Problem 7

Let ${p,q}$ be relatively prime positive integers. Prove that $${ \sum_{k=0}^{pq-1} (-1)^{\left\lfloor \frac{k}{p}\right\rfloor + \left\lfloor \frac{k}{q}\right\rfloor} = \begin{cases} 0 & \textnormal{ if } pq \textnormal{ is even} 1 & \textnormal{if } pq \textnormal{ odd}\end{cases}}$$

Proposed by Alexander Bolbot, State University, Novosibirsk.