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.

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