Josuke and Complete Graph
Contest: Codeforces Round 846 (Div. 2)
Difficulty rating: 2400
Tags: binary search, brute force, data structures, math, number theory

Josuke received a huge undirected weighted complete$$$^\dagger$$$ graph $$$G$$$ as a gift from his grandfather. The graph contains $$$10^{18}$$$ vertices. The peculiarity of the gift is that the weight of the edge between the different vertices $$$u$$$ and $$$v$$$ is equal to $$$\gcd(u, v)^\ddagger$$$. Josuke decided to experiment and make a new graph $$$G'$$$. To do this, he chooses two integers $$$l \le r$$$ and deletes all vertices except such vertices $$$v$$$ that $$$l \le v \le r$$$, and also deletes all the edges except between the remaining vertices.

Now Josuke is wondering how many different weights are there in $$$G'$$$. Since their count turned out to be huge, he asks for your help.

$$$^\dagger$$$ A complete graph is a simple undirected graph in which every pair of distinct vertices is adjacent.

$$$^\ddagger$$$ $$$\gcd(x, y)$$$ denotes the greatest common divisor (GCD) of the numbers $$$x$$$ and $$$y$$$.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of each test case contains two numbers $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le 10^{18}$$$, $$$l \le 10^9$$$).

Output format:
For each test case print a single number — the number of different weights among the remaining edges.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The graph $$$G'$$$ for the first test case.

The picture above shows that the graph has $$$2$$$ different weights.

In the fifth test case, there is only one vertex from which no edges originate, so the answer is $$$0$$$.

Example input:
7
2 4
16 24
2 6
1 10
3 3
2562 2568
125 100090

Example output:
2
6
3
5
0
5
50045

Editorial:
Давайте зафиксируем $$$g$$$ и проверим, что ребро веса $$$g$$$ существует в $$$G'$$$. Первое число, которое делится на $$$g$$$, начиная с $$$L$$$ — $$$\lceil \frac{L}{g} \rceil \cdot g$$$, а второе — $$$(\lceil \frac{L}{g} \rceil + 1) \cdot g$$$, заметим что их $$$gcd$$$ равен $$$g$$$. Если второе число больше $$$R$$$, то ребра веса $$$g$$$ в графе $$$G'$$$ не существует, потому что на отрезке с $$$L$$$ по $$$R$$$ больше нет способов найти ребро веса $$$g$$$. То есть надо посчитать количество таких $$$g$$$, что $$$(\lceil \frac{L}{g} \rceil + 1) \cdot g \leq R$$$.
Рассмотрим $$$g \geq L$$$, тогда $$$(\lceil \frac{L}{g} \rceil + 1) \cdot g = 2 \cdot g$$$. Получаем верхнее ограничение на $$$g \geq \lfloor \frac{R}{2} \rfloor$$$. То есть $$$L \leq g \leq \lfloor \frac{R}{2} \rfloor$$$ - удовлетворяют.
Остались $$$g < L$$$. В простой версии задаче, их можно было явно перебрать за $$$O(L)$$$.
Заметим, что $$$\lceil \frac{L}{g} \rceil$$$ принимает $$$O(\sqrt{L})$$$ значений. Тогда зафиксируем какое-то $$$f = \lceil \frac{L}{g} \rceil$$$, заметим, что $$$f$$$ соответствует последовательный отрезок значений $$$l \leq g \leq r$$$. Будем перебирать такие отрезки, поскольку их столько же, сколько и различных значений $$$f$$$, то есть $$$O(\sqrt{L})$$$. Тогда, если есть левая граница отрезка $$$l$$$, можно найти $$$r$$$ либо бинарным поиском, либо расписать формулу. Следующая левая граница будет просто $$$r + 1$$$. Тогда заметим, что если зафиксировано $$$f$$$, то $$$(f + 1) \cdot g \leq R$$$ равноценно $$$g \leq \lfloor \frac{R}{f + 1} \rfloor$$$. То есть при фиксированном отрезке с $$$l$$$ по $$$r$$$, $$$g$$$ удовлетворяет ограничению $$$l \leq g \leq min(r, \lfloor \frac{R}{f + 1} \rfloor)$$$.
Тогда получается решение за $$$O(\sqrt{L})$$$, которое проходит сложную версию задачи, или $$$O(\sqrt{L} \cdot log(L))$$$, что, если аккуратно написать, тоже проходит.