We have been given first $N$ natural numbers and asked to count all distinct pairs $(a,b)$ where, $a < b$ such that $a+b$ is divisible by a given number $M$.
Example: Given $N = 4$, i.e. $\{1,2,3,4\}$
$M = 3$
Only possible pairs satisfying above conditions are $(1,2)$ and $(2,4)$.
Since, $1 < 2$ and $1+2 = 3$ is divisible by $M$.
$2 < 4$ and $2+4 = 6$ is divisible by $M$.
Values $M$ and $N$ can be very large (of the order of $10^9$), so simply generating pairs and dividing won't work.
My Idea: We need to generate pairs which sum up to multiple of $M$. Since, there is a strict ordering between $a$ and $b.$ (i.e. $a < b$) so, for generating any number $x$ which lies in the range $1$ to $N$ there are $\frac{(x-1)}{2}$ possible pairs. So, we need to sum up these values over multiples of $M$. But when the value of $x$ goes beyond $N$, this idea doesn't work (as number of pairs decrease).
I can't proceed any further. Kindly guide me if I am in a wrong direction. Or suggest any other alternative to efficiently calculate the same.