Вы пришли на своё первое занятие по алгоритмам, где изучаете бинарный поиск. Вы слышали, как преподаватель рассуждал о том, почему бинарный поиск работает за $$$O(\log{n})$$$. Но вам хочется понять, нельзя ли получить лучшую оценку.
Дан отсортированный массив $$$a$$$ размера $$$n$$$ и целое число $$$k$$$. Определим $$$f(a, k, l, r)$$$ как результат выполнения следующего кода:
функция f(a, k, l, r):
если a не содержит k:
вернуть 0
mid = floor((l+r) / 2)
если a[mid]==k:
вернуть 1
иначе, если a[mid]<k:
вернуть 1+f(a, k, mid+1, r)
иначе:
вернуть 1+f(a, k, l, mid-1)
Вам даны два целых числа $$$n$$$ и $$$m$$$. Назовём массив $$$a$$$ хорошим, если:
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3 \leq n,m \leq 10^6$$$).
Гарантируется, что сумма всех $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$, и сумма всех $$$m$$$ по всем наборам входных данных также не превосходит $$$10^6$$$.
Для каждого набора входных данных выведите на отдельной строке требуемую сумму по модулю $$$676\,767\,677$$$.
73 33 43 54 34 5999967 9996715 876543
26601155031593903683322710644
В первом наборе входных данных одним из хороших массивов $$$a$$$ является $$$[2,2,3]$$$. Здесь $$$f(a,1,1,n)=0$$$ (так как $$$1$$$ отсутствует в $$$a$$$), $$$f(a,2,1,n)=1$$$, $$$f(a,3,1,n)=2$$$. Следовательно, вклад этого хорошего массива равен $$$0+1+2=3$$$.
