参考题解
题意：
T
T
T 组数据，每组数据给定
l
l
l 和
r
r
r
求有多少种
l
c
m
(
i
,
j
,
k
)
≥
i
+
j
+
k
lcm(i,j,k)\geq i+j+k
lcm(i,j,k)≥i+j+k，其中
l
≤
i
<
j
<
k
≤
r
l\leq i<j<k\leq r
l≤i<j<k≤r
数据范围：
1
≤
T
≤
5
,
1
≤
l
≤
r
≤
2
×
1
0
5
,
l
+
2
≤
r
1\leq T\leq 5, 1\leq l\leq r\leq 2\times 10^5,l+2\leq r
1≤T≤5,1≤l≤r≤2×105,l+2≤r
题解：
正难则反
考虑
l
c
m
(
i
,
j
,
k
)
<
i
+
j
+
k
lcm(i,j,k)<i+j+k
lcm(i,j,k)<i+j+k 的数量，其中
i
+
j
+
k
≤
3
k
−
2
<
3
k
i+j+k\leq 3k-2<3k
i+j+k≤3k−2<3k 。
计算出
l
c
m
(
i
,
j
,
k
)
<
3
k
lcm(i,j,k)<3k
lcm(i,j,k)<3k 的方案数，因为是最小公倍数，所以
l
c
m
(
i
,
j
,
k
)
lcm(i,j,k)
lcm(i,j,k) 只能为
k
k
k 或者
2
k
2k
2k。
-
l
c
m
(
i
,
j
,
k
)
=
k
lcm(i,j,k)=k
lcm(i,j,k)=k
f
a
c
[
k
]
fac[k]
fac[k] 表示
k
k
k 的因子，不包括
k
k
k 本身
从
f
a
c
[
k
]
fac[k]
fac[k] 中选择两个不同的因子，方案数为：
C
f
a
c
[
k
]
2
C_{fac[k]}^2
Cfac[k]2
-
l
c
m
(
i
,
j
,
k
)
=
2
k
lcm(i,j,k)=2k
lcm(i,j,k)=2k
这里的
i
i
i 和
j
j
j 都是
2
k
2k
2k 的因子，
l
c
m
(
i
,
j
,
k
)
=
2
k
<
i
+
j
+
k
lcm(i,j,k)=2k<i+j+k
lcm(i,j,k)=2k<i+j+k，故
i
+
j
>
k
i+j>k
i+j>k
-
因此
k
2
<
j
<
k
\frac{k}{2}<j<k
2k<j<k，令
j
=
2
k
t
j=\frac{2k}{t}
j=t2k
k
2
<
2
k
t
<
k
\frac{k}{2}<\frac{2k}{t}<k
2k<t2k<k，推得：
2
<
t
<
4
2<t<4
2<t<4，
t
=
3
t=3
t=3，因此
j
=
2
k
3
j=\frac{2k}{3}
j=32k
-
i
+
j
>
k
i+j>k
i+j>k 推得：
k
3
<
i
<
k
\frac{k}{3}<i<k
3k<i<k，令
i
=
2
k
t
i=\frac{2k}{t}
i=t2k
k
3
<
2
k
t
<
k
\frac{k}{3}<\frac{2k}{t}<k
3k<t2k<k，推得：
2
<
t
<
6
2<t<6
2<t<6，
t
=
3
t=3
t=3或
t
=
4
t=4
t=4 或
t
=
5
t=5
t=5，因此
i
=
2
k
3
i=\frac{2k}{3}
i=32k 或者
i
=
k
2
i=\frac{k}{2}
i=2k 或者
i
=
2
k
5
i=\frac{2k}{5}
i=52k，又因为
i
<
j
i<j
i<j，所以
i
=
k
2
i=\frac{k}{2}
i=2k 或者
i
=
2
k
5
i=\frac{2k}{5}
i=52k
通过上述分析得到：
j
=
2
k
3
j=\frac{2k}{3}
j=32k，
i
=
k
2
i=\frac{k}{2}
i=2k 或者
i
=
2
k
5
i=\frac{2k}{5}
i=52k
这是
l
c
m
(
i
,
j
,
k
)
=
2
k
lcm(i,j,k)=2k
lcm(i,j,k)=2k 的情况
由于数据组数很小，因此完全可以枚举 从
l
+
2
l+2
l+2 到
r
r
r 枚举
k
k
k
别忘了求的是
l
c
m
(
i
,
j
,
k
)
<
i
+
j
+
k
lcm(i,j,k)<i+j+k
lcm(i,j,k)<i+j+k 的数量。
这里可以用类似埃筛的方式筛出每个数的因子，时间复杂度为
O
(
n
log
n
)
O(n\log n)
O(nlogn) ，通过调和级数推导出
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200010;
ll f[N];
int l, r;
void solve() {
scanf("%d%d", &l, &r);
for (int i = l; i <= r; ++i) f[i] = 0;
for (int i = l; i < r; ++i)
for (int j = i * 2; j <= r; j += i)
f[j] += 1;
ll n = r - l + 1;
ll ans = n * (n - 1) * (n - 2) / 6;
for (int i = l + 2; i <= r; ++i) {
ans -= f[i] * (f[i] - 1) / 2;
if (i % 3) continue ;
if (i % 2 == 0 && i / 2 >= l) ans -= 1;
if (i % 5 == 0 && i / 5 * 2 >= l) ans -= 1;
}
printf("%lld\n", ans);
}
int main()
{
int T = 1;
scanf("%d", &T);
for (int i = 1; i <= T; ++i) {
solve();
}
return 0;
}
