Пусть N ≤ M. Если это не так поменяем значения местами, ответ не изменится. Тогда количество стаканчиков в пирамидке равно .

Для прохождения первой группы тестов достаточно было посчитать эту сумму с помощью цикла. Сложность такого решения O(t·min(N, M)).

Во второй группе тестов N = M, тогда , что в свою очередь при замене переменной j = N - i будет равно (общеизвестная формула). Сложность O(t), так как теперь на каждый запрос отвечаем за O(1).

Применим такую же замену в первоначальную формулу, получим . Таким образом мы получили две суммы, которые мы уже умеем считать по формулам. Получаем .

По полученной формуле видно, что ответ будет порядка N³. Соответственно, чтобы получить полный балл, нужно применить длинную арифметику.