## Question:

Recently I went to the Olympics, and there was a task:

The input is 3 positive natural numbers,

`l`

`r`

`a`

We need to find how many pairs of numbers from`l`

to`r`

(inclusive) can be made, but the sum of these 2 numbers must be a multiple of`а`

.For example: 3 numbers go to the input 1 5 2. The output is 4. Since you can make 4 pairs [1, 3] (1 + 3 = 4. 4 is divided by 2 without a remainder) [1,5] [2,4] [3,5].

If we solve this problem by enumeration, then for large numbers the program exceeds the time limit. I saw how someone solved this problem mathematically, but was too shy to find out the details.

## Answer:

Finding remainders after division

```
lm = l % a
rm = r % a
```

And quotients rounded up for the bottom border and down for the top

```
lq = (l + a - 1) // a
rq = r // a
```

If `rq > lq`

, then the interval `a*lq..a*rq-1`

contains all possible remainders `0..a-1`

`rq-lq`

times each, and there are still remainders in the ranges `lm..a-1`

and `0..rm`

Knowing the number of different residues, you can find the number of their pairwise sums, giving `0 или a`

For the given example, the remainder 0 occurs 2 times, the remainder 1 – 3 times. The number of pairs for the remainders `q`

and `aq`

will be `N(q)*N(aq)`

or `N(q)*(N(q)-1)/2`

in the case of `q=aq`

or `q=0`

, i.e. here `2*1/2 + 3*2/2 = 4`

For interval 2..11 and a=3 the answer will be `3*2/2+3*4=15`

, and for a=4 `2*1/2+3*2/2+3*2=10`