【树状数组该回炉重造了】Codeforces Round #813 (Div. 2) E2. LCM Sum (hard version)

参考题解

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

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

题解：
仍然是正难则反，考虑 $lcm(i,j,k)<i+j+k$ 的数量
开一个树状数组 $tr$ ，$tr[i]$ 用于维护三元组中 $i,j,k$的数量
具体是枚举 $k$，

• $lcm(i,j,k)=k$
  枚举 $k$ 的因子，第一层枚举 $i$，第二层枚举 $j$。
  经过计算双重枚举在 $2\times 10^5$ 范围内在 $3e7$ 左右，时限为 $3500ms$，实测跑 $480ms$。

• $lcm(i,j,k)=2k$，以下情况的证明

  第一种情况：$i=\frac{2k}{5},j=\frac{2k}{3}$
  第二种情况：$i=\frac{k}{2},j=\frac{2k}{3}$

代码：

#include 
using namespace std;

typedef long long ll;

const int N = 200010;
struct Node {
	int l, id;
};

vector<Node> a[N];
ll ans[N];
ll tr[N]; // 树状数组 tr[i] 表示以 i 开头的 (i,j,k)

const int MAXN = 200000;
const int MAXM = MAXN << 1; 
ll sum(int p) {
	ll res = 0;
	while (p > 0) {
		res += tr[p];
		p -= p & (-p);
	}
	return res;
}

void add(int p, ll x) {
	while (p <= MAXN) {
		tr[p] += x; 
		p += p & (-p);
	}
}

vector<int> fac[N];
int n;

int main()
{
	// 类似埃筛的 O(nlogn) 筛因子法
	for (int i = 1; i <= MAXN; ++i)
		for (int j = i * 2; j <= MAXN; j += i)
			fac[j].push_back(i);
	
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		int l, r;
		scanf("%d%d", &l, &r);
		a[r].push_back({l, i});
		ll x = r - l + 1;
		ans[i] = x * (x - 1) * (x - 2) / 6;
	}
	
	// 枚举 r，同时将这个 r 对应为 k 的所有的 (i, j, k) 累计到树状数组 tr[i] 中
	for (int r = 1; r <= MAXN; ++r) {
		for (int i = 0; i < fac[r].size(); ++i) {
			int x = fac[r][i];
			int cnt = 0;
			for (int j = i + 1; j < fac[r].size(); ++j) {
				int y = fac[r][j];
				if (r % x == 0 && r % y == 0) cnt += 1;
			}
			add(x, cnt);
		}
		
		// lcm(i,j,k)=2k, i=2k/5, j=2k/3
		if (r % 15 == 0) {
			int x = r / 5 * 2;
			int y = r / 3 * 2;
			add(x, 1);
		}
		// lcm(i,j,k)=2k, i=k/2, j=2k/3
		if (r % 6 == 0) {
			int x = r / 2;
			int y = r / 3 * 2;
			add(x, 1);
		}
		// 只统计 从 [l, r - 2] 内的 i 对应的方案数
		for(auto& u: a[r]) {
			ans[u.id] -= sum(r - 2) - sum(u.l - 1);
		}
	}
	
	for (int i = 1; i <= n; ++i) printf("%lld\n", ans[i]);
	
	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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85