Чем заменить перебор?

#python #олимпиада #задачи

Недавно ездил на олимпиаду, и там была задача:


  На вход поступает 3 положительных натуральных числа, l r a Нужно найти сколько
пар чисел от l до r (включительно) можно составить, но сумма этих 2 чисел должна быть
кратна числу а.
  
  Например: на вход идут 3 числа 1 5 2. На выход 4. Так как можно составить 4 пары
[1, 3](1+3=4. 4 делится на 2 без остатка)[1,5][2,4][3,5]. 


Если решать эту задачу перебором, то при больших числах программа превышает лимит
времени. Видел как кто-то решил данную задачу математически, но постеснялся узнать
подробности.
    

Ответы

Ответ 1

Находим остатки от деления

lm = l % a
rm = r % a


И частные, округленные вверх для нижней границы и вниз для верхней

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


Если rq > lq, то промежуток a*lq..a*rq-1 содержит все возможные остатки 0..a-1 в
количестве rq-lq раз каждый, и ещё имеются остатки в диапазонах lm..a-1 и 0..rm

Зная количество разных остатков, можно найти количество их попарных сумм, дающих 0 
 или a 

Для приведённого примера остаток 0 встречается 2 раза, остаток 1 - 3 раза. Количество
пар для остатков q и a-q будет N(q)*N(a-q) или N(q)*(N(q)-1)/2 в случае q=a-q или q=0,
т.е. здесь 2*1/2 + 3*2/2 = 4

Для промежутка 2..11 и a=3  ответ будет 3*2/2+3*4=15, a для a=4 2*1/2+3*2/2+3*2=10


Ответ 2

Исходя из того, что в ответе в парах одно число всегда меньше другого могу предложить
такой вариант.


Перебираете в цикле все значения i от l до r-l.
На каждом шаге:

2.1. находите такое минимально j, что i