Пусть N ≤ M. Если это не так поменяем значения местами, ответ не изменится. Тогда количество стаканчиков в пирамидке равно .
Для прохождения первой группы тестов достаточно было посчитать эту сумму с помощью цикла. Сложность такого решения O(t·min(N, M)).
Во второй группе тестов N = M, тогда , что в свою очередь при замене переменной j = N - i будет равно
(общеизвестная формула). Сложность O(t), так как теперь на каждый запрос отвечаем за O(1).
Применим такую же замену в первоначальную формулу, получим . Таким образом мы получили две суммы, которые мы уже умеем считать по формулам. Получаем
.
По полученной формуле видно, что ответ будет порядка N3. Соответственно, чтобы получить полный балл, нужно применить длинную арифметику.