Josuke and Complete Graph

题意翻译

### 题目描述 Josuke 收到了一个巨大的无向带权完全图 $G$ 作为他祖父的礼物。该图形包含$10^{18}$ 个顶点。 这个礼物的特点是不同顶点 $u$ 和 $v$ 之间的边的权重等于 $\gcd(u,v)$ 。 Josuke 决定制作一个新的图 $G'$。为此，他选择两个整数 $l\le r$ ，并删除除 $l\le v\le r$ 的顶点 $v$ 之外的所有顶点以及与其相连的边。 现在 Josuke 想知道 $G'$ 中有的边多少种不同的权重。 ### 输入格式 第 $1$ 行一个整数 $t\;(1\le t\le100)$ ，表示数据组数。 接下来 $t$ 行每行两个整数 $l,r\;(1\le l\le r\le10^{18},l\le10^9\;)$ ，表示一组数据中的 $l,r$ 。 ### 输出格式 每行一个整数，表示每组数据 $G'$ 中不同权重的边的数量。 Translated by @[w9095](https://www.luogu.com.cn/user/569235)

题目描述

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)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of the numbers $ x $ and $ y $ .

输入输出格式

输入格式

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 $ ).

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

2
6
3
5
0
5
50045

说明

 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 $ .

**题目大意：**

Josuke 收到了一个包含 $10^{18}$ 个顶点的无向带权完全图 $G$ 作为礼物。图中不同顶点 $u$ 和 $v$ 之间的边的权重等于 $\gcd(u,v)$。Josuke 制作了一个新图 $G'$，通过选择两个整数 $l \le r$，删除除了 $l \le v \le r$ 的顶点 $v$ 以及与其相连的边。任务是计算 $G'$ 中边的不同权重的数量。

**输入格式：**

第1行包含一个整数 $t \;(1 \le t \le 100)$，表示数据组数。接下来 $t$ 行，每行包含两个整数 $l, r \;(1 \le l \le r \le 10^{18}, l \le 10^9)$，表示一组数据中的 $l, r$。

**输出格式：**

对于每组数据，输出一行，包含一个整数，表示 $G'$ 中不同权重的边的数量。

**样例输入输出：**

**输入样例 #1：**
```
7
2 4
16 24
2 6
1 10
3 3
2562 2568
125 100090
```

**输出样例 #1：**
```
2
6
3
5
0
5
50045
```

**说明：**

这个题目是关于计算在一个特定范围内顶点的完全图中，边的不同权重的数量。权重是边的两个顶点之间的最大公约数。**题目大意：** Josuke 收到了一个包含 $10^{18}$ 个顶点的无向带权完全图 $G$ 作为礼物。图中不同顶点 $u$ 和 $v$ 之间的边的权重等于 $\gcd(u,v)$。Josuke 制作了一个新图 $G'$，通过选择两个整数 $l \le r$，删除除了 $l \le v \le r$ 的顶点 $v$ 以及与其相连的边。任务是计算 $G'$ 中边的不同权重的数量。 **输入格式：** 第1行包含一个整数 $t \;(1 \le t \le 100)$，表示数据组数。接下来 $t$ 行，每行包含两个整数 $l, r \;(1 \le l \le r \le 10^{18}, l \le 10^9)$，表示一组数据中的 $l, r$。 **输出格式：** 对于每组数据，输出一行，包含一个整数，表示 $G'$ 中不同权重的边的数量。 **样例输入输出：** **输入样例 #1：** ``` 7 2 4 16 24 2 6 1 10 3 3 2562 2568 125 100090 ``` **输出样例 #1：** ``` 2 6 3 5 0 5 50045 ``` **说明：** 这个题目是关于计算在一个特定范围内顶点的完全图中，边的不同权重的数量。权重是边的两个顶点之间的最大公约数。