把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

1712E2 LCM Sum(hard version)
题目大意：1e5个询问，给l,r(2e5)，求有多少三元组使其lcm>=元素和。

解：

第一眼先知道方向是
首先我们知道lcm肯定是最大数k的倍数，如果这个倍数>=3那么lcm肯定>和。为1肯定小于，而为2的时候呢？要是为2，那么i和j至少有一个是2k的因数，且i+j>k，可以发现这种条件仅当i=2x/4,j=2x/3或者i=2x/5,j=2x/3时可以满足，而这也就是倍数为2的所有情况。显然满足这种条件的k分别是6和15的倍数，那么这种元祖的数量就是r/6-(l-1)/3和r/15-(l-1)/6个。
接下来讨论倍数为1的情况，如果在easy version的t=5情况下，暴力就能n√n地把答案求出来，而t多了之后首先想到离线+区间的操作，这样的操作会给我们提出一个要求：我们需要在排序完，之后一边（假设是l）按顺序减小（r就是增加了）时需要通过另一个值（对应地是r）来O(能过)地求出这个区间的答案，在本题里，和r相关的显然是三元组里的k，而k可以是l+2到r区间内的任意一个数，所以肯定需要区间和来做到O(能过)求贡献数，这就要求区间里的每个点都是对应k的贡献。
那么k的贡献是什么，显然i和j都＜k，且当lcm=k时i和j都是k的因数，那么以k为结尾的三元组就是C(之前出现的因数数量,2)，也就是一个等差数列和，那么就可以实时维护。
按l从大到小排序的情况下，将一个cur从max(r)下移，为每个cur，枚举其所有倍数来维护这个等差数列和，把答案维护到区间数据结构里（单点修改），然后到cur=l的时候，查询区间(l,r)（或者(1,r)），然后维护答案。
之后用C(n,3)去减一下就能得到ans，复杂度为O(rlogn+nlogr)。

代码

代码
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182

#pragma comment(linker, "/STACK:102400000,102400000")
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
#define maxn 200005
#define ls o<<1
#define rs (o<<1)+1
#define endl '\n'
#define cfast ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
#define mdl 998244353
#define inc(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
//----------------------------------------------------------------------------------------------------------------------//
template<typename t1, typename t2>
void debug(t1 x, t2 y) {
	cout << x << " : " << y << endl;
}
template<typename t1>
void debug(t1 x) {
	inc(i, 0, x.size()) {
		cout << x[i] << " ";
	}cout << endl;
}
template<typename t1>
void debug(t1 x, int l, int r) {
	inc(i, l, r) {
		cout << x[i] << " ";
	}cout << endl;
}
ll cpow(ll x, ll n, ll md) {
	int ans = 1;
	while (n > 0) {
		if (n & 1) ans = (ans * x) % md;
		x = (x * x) % md;
		n >>= 1;
	}
	return ans;
}
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0)return a;
	else return gcd(b, a % b);
}
ll string2ll(string s) {
	ll tmp = 1;
	ll res = 0;
	for (int i = s.length() - 1; i >= 0; i--) {
		res += (ll)(s[i] - '0') * tmp;
		tmp *= 10ll;
	}
	return res;
}
string ll2string(ll num) {
	string res = "";
	while (num) {
		res += (char)(num % 10 + '0');
		num /= 10;
	}
	reverse(res.begin(), res.end());
	return res;
}
ll f[300005], inv[300005];
void inif() {
	f[0] = inv[0] = 1;
	for (ll i = 1; i <= 300000; i++) {
		f[i] = f[i - 1] * i % mdl;
		inv[i] = cpow(f[i], mdl - 2, mdl);
	}
}
inline ll C(ll n, ll m) {
	if (m > n)return 0;
	return f[n] * inv[m] % mdl * inv[n - m] % mdl;
}

struct ST {
	ll st[maxn * 4], a[maxn],tag[maxn*4];
	void build(int o, int l, int r) {
		if (l == r) {
			st[o] = a[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(ls, l, mid);
		build(rs, mid + 1, r);
		st[o] = st[ls]+ st[rs];
	}
	void push_down(int o, int l, int r) {
		int mid = (l + r) / 2;
		if (tag[o]) {
			tag[rs] += tag[o];
			tag[ls] += tag[o];
			st[ls] += (mid - l + 1) * tag[ls];
			st[rs] += (r - mid) * tag[rs];
			tag[o] = 0;
		}
	}
	void push_up(int o) {
		st[o] = st[ls] + st[rs]; 
	}
	void queryadd(int o, int l, int r, int ql, int qr,ll val) {
		
		if (ql <= l && r <= qr) {
			tag[o] += val;
			st[o] += (r - l + 1) * val;
			return;
		}
		push_down(o, l, r);
		int mid = (l + r) >> 1;
		if (ql <= mid)queryadd(ls, l, mid, ql, qr, val);
		if (qr > mid)queryadd(rs, mid + 1, r, ql, qr, val);
		push_up(o);
	}
	ll querysum(int o, int l, int r, int ql, int qr) {
		if (ql <= l && r <= qr) {
			return st[o];
		}
		push_down(o, l, r);
		int mid = (l + r) >> 1;
		ll ans = 0;
		if (ql <= mid)ans+=querysum(ls, l, mid, ql, qr);
		if (qr > mid)ans+=querysum(rs, mid + 1, r, ql, qr);
		return ans;
	}
}st;
struct ttm {
	int l, r, num;
	friend bool operator<(ttm t1, ttm t2) {
		return t1.l > t2.l;
	}
}ques[maxn];
ll ans[maxn];
ll num[maxn];
vector<int> facs;
int main() {
	cfast;
	int t = 1;

	//inif();
	cin >> t;
	inc(tt, 0, t) {
		cin >> ques[tt].l >> ques[tt].r;
		ques[tt].num = tt;
		ll n = ques[tt].r - ques[tt].l + 1;
		ans[tt] = n * (n - 1) * (n - 2) / 6;
		ans[tt] -= max(0, ques[tt].r / 6 - (ques[tt].l-1) / 3) + max(0, ques[tt].r / 15 - (ques[tt].l-1) / 6);
	}
	sort(ques, ques + t);
	
	st.build(1, 1, 2e5);
	
	//cout << st.querysum(1, 1, 2e5, 1, 10);
	int now = 2e5;
	inc(i, 0, t) {
		while (now >= ques[i].l) {
			ll base = now;
			for (ll j = now * 2; j <= 2e5; j += base) {
				st.queryadd(1, 1, 2e5, j, j, num[j]);
				num[j]++;
			}
			now--;
		}
	
		ans[ques[i].num] -= st.querysum(1, 1, 2e5, 1, ques[i].r);
	}
	inc(i, 0, t) {
		cout << ans[i] << endl;
	}
}
/*
6 2
5 5 10 10 5 5
6 3
5 5 10 10 5 5
*/