Suspicious logarithms (Codeforces 1891D)
Tags: Math, binary search

Let $$$f$$$($$$x$$$) be the floor of the binary logarithm of $$$x$$$. In other words, $$$f$$$($$$x$$$) is largest non-negative integer $$$y$$$, such that $$$2^y$$$ does not exceed $$$x$$$.Let $$$g$$$($$$x$$$) be the floor of the logarithm of $$$x$$$ with base $$$f$$$($$$x$$$). In other words, $$$g$$$($$$x$$$) is the largest non-negative integer $$$z$$$, such that $$${f(x)}^{z}$$$ does not exceed $$$x$$$.You are given $$$q$$$ queries. The $$$i$$$-th query consists of two integers $$$l_i$$$ and $$$r_i$$$. The answer to the query is the sum of $$$g$$$($$$k$$$) across all integers $$$k$$$, such that $$$l_i \leq k \leq r_i$$$. Since the answers might be large, print them modulo $$${10^9 + 7}$$$.

Input: The first line contains a single integer $$$q$$$ — the number of queries ($$$1 \leq q \leq 10^5$$$).The next $$$q$$$ lines each contain two integers $$$l_i$$$ and $$$r_i$$$ — the bounds of the $$$i$$$-th query ($$$4 \leq l_i \leq r_i \leq 10^{18}$$$). 

Output: For each query, output the answer to the query modulo $$$10^9 + 7$$$.

Note: The table below contains the values of the functions $$$f$$$($$$x$$$) and $$$g$$$($$$x$$$) for all $$$x$$$ such that $$$1 \leq x \leq 8$$$.  $$$x$$$$$$1$$$$$$2$$$$$$3$$$$$$4$$$$$$5$$$$$$6$$$$$$7$$$$$$8$$$$$$f$$$$$$0$$$$$$1$$$$$$1$$$$$$2$$$$$$2$$$$$$2$$$$$$2$$$$$$3$$$$$$g$$$$$$-$$$$$$-$$$$$$-$$$$$$2$$$$$$2$$$$$$2$$$$$$2$$$$$$1$$$ 

Sample Inputs:
12
4 6
4 7
4 8
4 100000
179 1000000000000000000
57 179
4 201018959
7 201018960
729 50624
728 50624
728 50625
729 50625

Sample Outputs:
6
8
9
348641
41949982
246
1
0
149688
149690
149694
149692

Solution (Python):
from bisect import bisect_right

def g(n):
    res1 = 0
    res = 0
    while 2 ** res1 <= n:
        res1 += 1
    res1 -= 1
    while res1 ** res <= n:
        res += 1
    return res - 1

def find(n, lo, hi):
    while lo < hi:
        mid = (lo + hi) // 2
        if g(mid) >= n:
            hi = mid
        else:
            lo = mid + 1
    return lo
lst = [4]
value = [2]
for i in range(3, 59):
    u = g(2 ** i)
    v = g(2 ** (i + 1) - 1)
    x = 0
    if u == value[-1]:
        if v > u:
            x = find(v, 2 ** i, 2 ** (i + 1) - 1)
            lst.append(x)
            value.append(v)
    elif u == v:
        lst.append(2 ** i)
        value.append(u)
    else:
        x = find(v, 2 ** i, 2 ** (i + 1) - 1)
        lst.extend([2 ** i, x])
        value.extend([u, v])
m = len(lst)
kq = [value[i] * (lst[i + 1] - lst[i]) for i in range(m - 1)]

def solve(l, r):
    u = bisect_right(lst, l) - 1
    v = bisect_right(lst, r) - 1
    res = 0
    if u < v:
        for i in range(u + 1, v):
            res += kq[i]
        res += value[u] * (lst[u + 1] - l)
        res += value[v] * (r - lst[v] + 1)
    else:
        res += value[u] * (r - l + 1)
    return res
for q in range(int(input())):
    (l, r) = map(int, input().split())
    print(solve(l, r) % (10 ** 9 + 7))

Solution (Python):
p = 10 ** 9 + 7
base = {}
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(x):
    if x in base:
        return base[x]
    l = 0
    r = 67
    while l <= r:
        m = (l + r) // 2
        if 1 << m <= x:
            l = m + 1
        else:
            r = m - 1
    base[x] = r
    return r
lk = {}

def get(k):
    if k in lk:
        return lk[k]
    l = 0
    r = 67
    x = 1 << k
    while l <= r:
        m = (l + r) // 2
        if k ** m <= x:
            l = m + 1
        else:
            r = m - 1
    z = r
    t = k ** (z + 1)
    if t >= 1 << k + 1:
        t = 1 << k + 1
    lk[k] = (z, t)
    return lk[k]

def get_sum(k, end):
    (z, t) = get(k)
    if t > end:
        pl = (end - (1 << k) + 1) % p
        return z * pl % p
    else:
        pl1 = (t - (1 << k)) % p
        pl2 = (end - t + 1) % p
        return (z * pl1 % p + (z + 1) * pl2 % p) % p
pq = {}
for k in range(2, 67):
    pq[k] = get_sum(k, (1 << k + 1) - 1)

def solve():
    (li, ri) = map(int, input().split())
    (xi, yi) = (f(li), f(ri))
    if xi == yi:
        ans = get_sum(xi, ri)
        if li > 1 << xi:
            ans = ans + p - get_sum(xi, li - 1)
            ans = ans % p
        print(ans)
        return
    ans = 0
    ans += pq[xi]
    if li > 1 << xi:
        ans = ans + p - get_sum(xi, li - 1)
        ans = ans % p
    ans += get_sum(yi, ri)
    ans = ans % p
    for z in range(xi + 1, yi):
        ans += pq[z]
        ans = ans % p
    print(ans)
T = int(input())
for _ in range(T):
    solve()

Solution (Python):
from bisect import bisect_right

def g(n):
    res1 = 0
    res = 0
    while 2 ** res1 <= n:
        res1 += 1
    res1 -= 1
    while res1 ** res <= n:
        res += 1
    return res - 1

def find(n, lo, hi):
    while lo < hi:
        mid = (lo + hi) // 2
        if g(mid) >= n:
            hi = mid
        else:
            lo = mid + 1
    return lo
lst = [4]
value = [2]
for i in range(3, 59):
    u = g(2 ** i)
    v = g(2 ** (i + 1) - 1)
    x = 0
    if u == value[-1]:
        if v > u:
            x = find(v, 2 ** i, 2 ** (i + 1) - 1)
            lst.append(x)
            value.append(v)
    elif u == v:
        lst.append(2 ** i)
        value.append(u)
    else:
        x = find(v, 2 ** i, 2 ** (i + 1) - 1)
        lst.extend([2 ** i, x])
        value.extend([u, v])
m = len(lst)
kq = [value[i] * (lst[i + 1] - lst[i]) for i in range(m - 1)]

def solve(l, r):
    u = bisect_right(lst, l) - 1
    v = bisect_right(lst, r) - 1
    res = 0
    if u < v:
        for i in range(u + 1, v):
            res += kq[i]
        res += value[u] * (lst[u + 1] - l)
        res += value[v] * (r - lst[v] + 1)
    else:
        res += value[u] * (r - l + 1)
    return res
for q in range(int(input())):
    (l, r) = map(int, input().split())
    print(solve(l, r) % (10 ** 9 + 7))