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

Three positive positive integers arrive at the input, l r a It is necessary to find how many pairs of numbers from l to r (inclusive) can be composed, but the sum of these 2 numbers must be a multiple of the number а .

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

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

  • one
    And why the result is no pairs [1,1], [2,2], [3,3], [4,4] and [5,5]? - German Borisov

2 answers 2

Find the remainder of the division

 lm = l % a rm = r % a

And private, rounded up for lower bound and down for upper

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

If rq > lq , then the interval a*lq..a*rq-1 contains all possible residues 0..a-1 in the number of rq-lq once each, and there are still residues in the ranges lm..a-1 and 0..rm

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

For the given example, the remainder 0 occurs 2 times, the remainder 1-3 times. The number of pairs for the residues q and aq will be N(q)*N(aq) or N(q)*(N(q)-1)/2 in the case q=aq or q=0 , i.e. here 2*1/2 + 3*2/2 = 4

For the interval 2..11 and a = 3 the answer will be 3*2/2+3*4=15 2/2 3*2/2+3*4=15 , a for a = 4 2*1/2+3*2/2+3*2=10 2/2 2*1/2+3*2/2+3*2=10

    Based on the fact that in the answer in pairs one number is always less than another I can offer this option.

    1. Looping through the loop all values ​​of i from l to rl .

    2. At each step:

      2.1. find a minimum j such that i < j <= r and i+j multiple of a .

      2.2. Enumerate all numbers j , j+a , j+2a ... j+na until j+na <= r . The pair [ i , j+na ] is the desired pair.

    If only quantity is needed, then j and n can be calculated mathematically.