【关系推导】Codeforces Round #813 (Div. 2) E1. LCM Sum (easy version)

参考题解

题意：
$T$ 组数据，每组数据给定 $l$ 和 $r$
求有多少种 $lcm(i,j,k)\ge i+j+k$，其中$l\le i<j<k\le r$

数据范围：$1\le T\le 5,1\le l\le r\le 2\times 10^5,l+2\le r$

题解：
正难则反
考虑 $lcm(i,j,k)<i+j+k$ 的数量，其中 $i+j+k\le 3k-2<3k$ 。
计算出 $lcm(i,j,k)<3k$ 的方案数，因为是最小公倍数，所以 $lcm(i,j,k)$ 只能为 $k$ 或者 $2k$。

• $lcm(i,j,k)=k$
  $fac[k]$ 表示 $k$ 的因子，不包括 $k$ 本身
  从 $fac[k]$ 中选择两个不同的因子，方案数为：$C_{fac[k]}^2$

• $lcm(i,j,k)=2k$
  这里的 $i$ 和 $j$ 都是 $2k$ 的因子，$lcm(i,j,k)=2k<i+j+k$，故 $i+j>k$

  • 因此 $\frac{k}{2}<j<k$，令 $j=\frac{2k}{t}$
    $\frac{k}{2}<\frac{2k}{t}<k$，推得：$2<t<4$，$t=3$，因此 $j=\frac{2k}{3}$

  • $i+j>k$ 推得：$\frac{k}{3}<i<k$，令 $i=\frac{2k}{t}$
    $\frac{k}{3}<\frac{2k}{t}<k$，推得：$2<t<6$，$t=3$或 $t=4$ 或 $t=5$，因此 $i=\frac{2k}{3}$ 或者 $i=\frac{k}{2}$ 或者 $i=\frac{2k}{5}$，又因为 $i<j$，所以 $i=\frac{k}{2}$ 或者 $i=\frac{2k}{5}$

  通过上述分析得到：$j=\frac{2k}{3}$，$i=\frac{k}{2}$ 或者 $i=\frac{2k}{5}$
  这是 $lcm(i,j,k)=2k$ 的情况

由于数据组数很小，因此完全可以枚举 从 $l+2$ 到 $r$ 枚举 $k$
别忘了求的是 $lcm(i,j,k)<i+j+k$ 的数量。

这里可以用类似埃筛的方式筛出每个数的因子，时间复杂度为 $O(n\log n)$ ，通过调和级数推导出

代码：

#include 
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37