Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
An exact duplicate of this question deleted by Qiaochu. Note that this is an open contest question, and someone seeking a full solution from outsiders might be considered cheating by that forum. –  anon May 7 '12 at 15:05
    
@anon: Thanks for pointing that out! I thought at first that it was a duplicate as well, but couldn't find the earlier question, and I thought I was probably mistaken, as there are other similar but non-identical questions around. –  Tara B May 7 '12 at 15:11
3  
@anon Thanks for pointing that out. I think that is the best that can be done in these cases, since that allows each person to make there choice how to vote, answer, etc. Some members feel strongly that rules stemming from the source of the problem should not be our concern (whether it be tests, online contests, etc). –  Bill Dubuque May 7 '12 at 15:13
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. –  Tara B May 7 '12 at 15:19
add comment

1 Answer

up vote 4 down vote accepted

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$?

share|improve this answer
    
I know. What makes you think I was saying anything about generating all pairs? –  Tara B May 7 '12 at 14:42
1  
then i am not getting what you said :( ... could u please tell more –  John Smith May 7 '12 at 14:44
    
Sure. I can't tell much about your mathematical background from your profile. Do you know about modular arithmetic? –  Tara B May 7 '12 at 14:45
    
yes... i know about what they do –  John Smith May 7 '12 at 14:54
    
(I believe you mean $\bmod M$ in the definition of $S_a$.) And if $M>N$? –  anon May 7 '12 at 15:10
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.