A6912. LCM Sum（hard version）
编程题
省选/NOI-
知识点
题目描述
我们之和，因我们众多。
给定两个正整数 $l$ 和 $r$。
请计算有多少个不同的整数三元组 $(i,j,k)$ 满足 $l \le i < j < k \le r$ 且 $\operatorname{lcm}(i,j,k) \ge i + j + k$。
这里 $\operatorname{lcm}(i,j,k)$ 表示整数 $i$、$j$、$k$ 的最小公倍数。
给定两个正整数 $l$ 和 $r$。
请计算有多少个不同的整数三元组 $(i,j,k)$ 满足 $l \le i < j < k \le r$ 且 $\operatorname{lcm}(i,j,k) \ge i + j + k$。
这里 $\operatorname{lcm}(i,j,k)$ 表示整数 $i$、$j$、$k$ 的最小公倍数。
输入格式
每个测试点包含多组测试数据。第一行包含测试用例数 $t$（$1 \le t \le 10^5$）。
接下来每组测试数据一行，包含两个整数 $l$ 和 $r$（$1 \le l \le r \le 2 \cdot 10^5$，$l + 2 \le r$）。
接下来每组测试数据一行，包含两个整数 $l$ 和 $r$（$1 \le l \le r \le 2 \cdot 10^5$，$l + 2 \le r$）。
输出格式
对于每组测试数据，输出一个整数，表示满足条件的三元组数量。
输入输出样例
输入 #1
5 1 4 3 5 8 86 68 86 6 86868
输出 #1
3 1 78975 969 109229059713337
说明/提示
## 说明/提示
在第一个测试用例中，有 $ 3 $ 个满足条件的三元组：
- $(1,2,3)$，
- $(1,3,4)$，
- $(2,3,4)$。
在第二个测试用例中，有 $ 1 $ 个满足条件的三元组：
- $(3,4,5)$。
在第一个测试用例中，有 $ 3 $ 个满足条件的三元组：
- $(1,2,3)$，
- $(1,3,4)$，
- $(2,3,4)$。
在第二个测试用例中，有 $ 1 $ 个满足条件的三元组：
- $(3,4,5)$。