# python – How to replace override?

## 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.

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`

Scroll to Top