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 froml
tor
(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