5
$\begingroup$

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.

  • 3
    I'm really not sure that deleting such questions is helpful. If the question had not been deleted, then I would have found it in my search for a duplicate, and then I would have known it was a contest question already before providing a partial answer.2012-05-07

1 Answers 1

4

Hint: Think of it as finding pairs $(a,b)$ such that $a+b\equiv 0 \mod M$.

We can write $N = Mq + r$ for some integers $q\geq 0$ and $0\leq r < M$. Now partition the integers from $1$ to $N$ into equivalence classes modulo $M$. For $0\leq a\leq M-1$, let $S_a = \{i\in [N] \mid i\equiv a \mod M\}$. Then $S_a$ contains $q+1$ elements for $0\leq a\leq r$, and $q$ elements for $r+1\leq a\leq M-1$.

Now, given $a\in [N]$, how many choices for $b$ are there such that $a+b\equiv 0 \mod M$?

  • 0
    Yes, you're right. My confusion.2012-05-07