Гармонический ряд

Пусть n = r - l + 1. Для начала рассмотрим решение за времени и памяти. Посчитаем R = (l·(l + 1)·(l + 2)... (r - 1)·r) - 1 при помощи бинарного возведения в степень за . Теперь предподсчитаем следующие величины: pi = l·(l + 1)·...·(i - 1)·i и si = i·(i + 1)·(i + 2)·...·(r - 1)·r. Заметим, что тогда x - 1 = R·px - 1·sx + 1 и мы можем посчитать нужную сумму за .

Для уменьшения потребления памяти разобьем отрезок от l до r на блоки размера , на каждом посчитаем произведение всех чисел в нем и посчитаем префиксные и суффиксные произведения этих величин. Будем решать для каждого блока отдельно. Посчитаем префиксные и суффиксные произведения в каждом блоке и домножим их на префиксные и суффиксные произведения предыдущего и следующего блока. Таким образом наше решение будет работать за времени и памяти.