思路与方法

条件等价

设 d 为四元组最大值，则条件

max(a,b,c,d) = lcm(a,b,c,d)

等价于

lcm(a,b,c,d) = d

而 lcm(x,d)=d 当且仅当 x | d。因此只需 a、b、c 都是 d 的约数（且 < d）。 于是问题转化为：

对每个 d ∈ [l,r]，统计其在区间 [l,d) 内的约数个数为 k，对该 d 贡献 C(k,3)（从这些约数中选出有序的 a<b<c）。

最终答案为

sum_{d=l..r} C(k_d, 3)

其中 k_d = # { x | d, l ≤ x < d }。

预处理

r ≤ 1e5，可以筛出每个 d 的真约数（< d）列表：

for i in [1..MAX]:
    for j in [2*i, 3*i, ..., MAX]:
        divs[j].push_back(i)

按 i 递增加入，divs[j] 自然有序。

回答查询

对一个区间 [l,r]：

• 遍历 d = l..r；
• 在 divs[d] 中用二分找到第一个 ≥ l 的位置，得到 k = size - pos；
• 若 k ≥ 3，把 C(k,3) = k*(k-1)*(k-2)/6 加到答案。

复杂度

• 预处理：O(MAX log MAX) 近似为 N * (1/1 + 1/2 + ... ) ≈ N log N)；
• 每次查询：遍历区间 O(r-l+1)，每个 d 二分 O(log τ(d))，总体约 O((r-l+1) log log r)，远小于 1e7 级别，t ≤ 10 轻松通过。
• 空间：存所有真约数，约 N log N 量级。

代码

Python

import sys
from bisect import bisect_left

# 读取全部输入
data = sys.stdin.read().strip().split()
it = iter(data)
t = int(next(it))

MAXN = 100000

# 预处理每个数的真约数(不含自身)，升序
divs = [[] for _ in range(MAXN + 1)]
for i in range(1, MAXN + 1):
    step = i
    j = i + step
    while j <= MAXN:
        divs[j].append(i)
        j += step

def comb3(k: int) -> int:
    # 计算 C(k,3)
    return k * (k - 1) * (k - 2) // 6

out = []
for _ in range(t):
    l = int(next(it)); r = int(next(it))
    ans = 0
    for d in range(l, r + 1):
        arr = divs[d]
        # 统计位于 [l, d) 的约数个数
        p = bisect_left(arr, l)  # 第一个 >= l 的位置
        k = len(arr) - p
        if k >= 3:
            ans += comb3(k)
    out.append(str(ans))

print("\n".join(out))

Java

import java.io.*;
import java.util.*;

public class Main {
    static final int MAXN = 100000;
    static ArrayList<Integer>[] divs = new ArrayList[MAXN + 1];

    static long comb3(int k) { // C(k,3)
        return 1L * k * (k - 1) * (k - 2) / 6;
    }

    // 二分找第一个 >= key 的下标
    static int lowerBound(ArrayList<Integer> a, int key) {
        int l = 0, r = a.size();
        while (l < r) {
            int m = (l + r) >>> 1;
            if (a.get(m) >= key) r = m;
            else l = m + 1;
        }
        return l;
    }

    public static void main(String[] args) throws Exception {
        // 预处理真约数
        for (int i = 0; i <= MAXN; i++) divs[i] = new ArrayList<>();
        for (int i = 1; i <= MAXN; i++) {
            for (int j = i + i; j <= MAXN; j += i) divs[j].add(i);
        }

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        for (int tc = 0; tc < T; tc++) {
            String[] parts = br.readLine().trim().split("\\s+");
            int l = Integer.parseInt(parts[0]);
            int r = Integer.parseInt(parts[1]);
            long ans = 0;
            for (int d = l; d <= r; d++) {
                ArrayList<Integer> arr = divs[d];
                int pos = lowerBound(arr, l);
                int k = arr.size() - pos; // [l, d) 内的约数个数
                if (k >= 3) ans += comb3(k);
            }
            sb.append(ans).append('\n');
        }
        System.out.print(sb.toString());
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000;
vector<int> divs[MAXN + 1];

long long comb3(long long k) { // C(k,3)
    return k * (k - 1) * (k - 2) / 6;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 预处理每个数的真约数
    for (int i = 1; i <= MAXN; ++i) {
        for (int j = i + i; j <= MAXN; j += i) divs[j].push_back(i);
    }

    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int l, r; 
        cin >> l >> r;
        long long ans = 0;
        for (int d = l; d <= r; ++d) {
            auto &arr = divs[d];
            // 统计位于 [l, d) 的约数个数：lower_bound 找到第一个 >= l
            int pos = lower_bound(arr.begin(), arr.end(), l) - arr.begin();
            int k = (int)arr.size() - pos;
            if (k >= 3) ans += comb3(k);
        }
        cout << ans << "\n";
    }
    return 0;
}

题目内容

给定两个正整数 $l$ 和 $r$ ，请统计满足以下条件的四元组 $(a,b,c,d)$ 的个数：

• $l≤a<b<c<d≤r$ ;

• $max(a, b,c,d)= lcm(a, b, c,d)$ 。

【名词解释】

最小公倍数(lcm)：指两个或多个整数公有的倍数中最小的一个。例如，$8$ 和 $12$ 的最小公倍数是 $24$ ，因此记作 $lcm(8,12)= 24$ 。

输入描述

第一行输入整数 $t(1 ≤t≤ 10)$ ，表示测试用例数；

接下来 $t$ 行，每行输入两个整数 $l$ 和 $r(1≦l≦r≦ 10^5,r-l+1≥ 4)$ ，表示区间端点。

输出描述

对于每个测试用例，在一行输出一个整数，表示满足条件的四元组个数。

样例1

输入

3
1 10
3 6
1 10000

输出

3
0
4672113

说明

在第一个测试用例中，符合条件的四元组有 $(1,2,3,6),(1,2,4,8),(1,2,5,10)$ , 共 $3$ 个；

在第二个测试用例中，没有符合条件的四元组。