Sum of two elements in set evenly divisible by k
This solution actually works in time $O(n+k)$. The idea is to maintain an array $m_0,\ldots,m_{k-1}$, where $m_r$ is the number inputs seen so far which leave a remainder of $r$ after division by $k$. When we see a new input which leaves a remainder of $r$ after division by $k$, we count $m_{k-r}$ new pairs (where $m_k = m_0$), and then update the array $m$.

A simpler solution is to first compute a histogram $m_0,\ldots,m_{k-1}$, where $m_r$ is the number of inputs in total which leave a remainder of $r$ after division by $k$. For each pair $s+t = k$, we count $m_sm_t/2$ pairs, and for $s=t=0$, we count $m_0(m_0-1)/2$ pairs (exercise), for a total of
$$ \frac{m_0(m_0-1)}{2} + \sum_{s=1}^{\lfloor k/2 \rfloor} \frac{m_sm_t}{2}. $$