Codeforces Round 907 (Div. 2) |
---|
Finished |
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}$$$.
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}$$$).
For each query, output the answer to the query modulo $$$10^9 + 7$$$.
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
6 8 9 348641 41949982 246 1 0 149688 149690 149694 149692
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$$$ |
Name |
---|