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
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
| \documentclass{article}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{xeCJK}
\usepackage{multicol}
\usepackage{tocloft}
\usepackage{xcolor}
\usepackage[cachedir=_minted-main]{minted}
\usepackage[a4paper, left=2cm, right=2cm, top=2.5cm, bottom=2.5cm]{geometry}
\usepackage{tikz}
\usetikzlibrary{arrows.meta, positioning, decorations.pathreplacing}
\setminted{
breaklines=true,
breakanywhere=true,
fontsize=\small,
frame=single,
bgcolor=gray!5,
tabsize=2,
}
\renewcommand{\cftsecleader}{\cftdotfill{\cftdotsep}}
\usepackage[colorlinks=true, linkcolor=black, anchorcolor=black, citecolor=black, filecolor=black, menucolor=black, runcolor=black, urlcolor=blue]{hyperref}
\definecolor{gcdc}{RGB}{50,120,200}
\definecolor{maxc}{RGB}{220,80,60}
\definecolor{accc}{RGB}{0,160,80}
\definecolor{blockbg}{RGB}{230,240,255}
\title{1009 GCD 题解}
\author{Gospel\_rock}
\date{}
\begin{document}
\maketitle
\section{题意}
给定两个长度为 $n$ 的整数数组 $a$ 和 $b$。$q$ 次询问，每次给出区间 $[l, r]$，取出子数组 $a' = a[l \dots r]$，$b' = b[l \dots r]$（长度 $m = r - l + 1$）。
每次操作可以选取下标 $i$（$1 \le i \le m$），计算后缀 GCD $g_i = \gcd(a'_i, a'_{i+1}, \ldots, a'_m)$，然后将 $b'_j$ 减去 $g_i$（对所有 $i \le j \le m$）。每次操作代价为 $1$。求使 $b'$ 所有元素 $\le 0$ 的最小总代价。
\section{贪心策略}
\subsection{关键观察：后缀 GCD 的单调性}
后缀 GCD 满足 $g_1 \mid g_2 \mid \cdots \mid g_m$，因此 $g_1 \le g_2 \le \cdots \le g_m$。这意味着越靠右的位置，单次操作的减法力度越大。
\subsection{贪心方案}
从左到右扫描位置 $k = 1, 2, \ldots, m$，维护一个累积减量 $S$（初始 $S = 0$）。$S$ 表示之前所有操作对位置 $k$ 产生的总减量。
\begin{quote}
若 $b'_k > S$，则在位置 $k$ 追加 $c = \left\lceil \dfrac{b'_k - S}{g_k} \right\rceil$ 次操作，随后更新 $S \leftarrow S + c \cdot g_k$。
\end{quote}
\subsection{为什么在当前位置操作？}
当扫到位置 $k$ 时，如果 $b'_k > S$，说明之前的操作不够用，必须追加。追加操作可以在 $1$ 到 $k$ 的任何位置执行。但由于 $g_k \ge g_j$（$\forall\, j \le k$），在位置 $k$ 执行单次操作的减量最大。
同时，位置 $1$ 到 $k - 1$ 已经在之前的步骤中被满足了，所以我们不需要利用"更早位置能覆盖更多左侧元素"这一优势——那些左侧元素早已被处理完毕。
综合来看：在位置 $k$ 追加操作，既享受了最大的单次减量 $g_k$，又不浪费在已满足的左侧位置上。而且这些操作也会对 $k$ 之后的所有位置产生减量，为后续处理提供帮助。
\subsection{样例验证}
以询问 $[1, 3]$ 为例：$a' = [6, 12, 18]$，$b' = [10, 20, 30]$。
后缀 GCD：$g_1 = \gcd(6, 12, 18) = 6$，$g_2 = \gcd(12, 18) = 6$，$g_3 = 18$。
\begin{itemize}
\item $k = 1$：$S = 0 < b'_1 = 10$。追加 $\lceil 10 / 6 \rceil = 2$ 次。$S \leftarrow 12$。代价 $= 2$。
\item $k = 2$：$S = 12 < b'_2 = 20$。追加 $\lceil 8 / 6 \rceil = 2$ 次。$S \leftarrow 24$。代价 $= 4$。
\item $k = 3$：$S = 24 < b'_3 = 30$。追加 $\lceil 6 / 18 \rceil = 1$ 次。$S \leftarrow 42$。代价 $= 5$。
\end{itemize}
总代价为 $5$，与样例吻合。
图~\ref{fig:greedy} 展示了上述过程。
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[>=Stealth, scale=1.1]
\foreach \k/\gv/\bv in {1/6/10, 2/6/20, 3/18/30} {
\node[font=\small, above] at (\k * 2.5, 2.7) {$k = \k$};
\node[gcdc, font=\small] at (\k * 2.5, 2.2) {$g_{\k} = \gv$};
\node[maxc, font=\small] at (\k * 2.5, 1.7) {$b'_{\k} = \bv$};
}
\draw[accc, very thick, -Stealth] (1.5, 0.8) -- (2.5, 0.8) node[midway, above, font=\scriptsize, accc] {$+2 \times 6$};
\node[accc, font=\small] at (1.2, 0.8) {$S\!=\!0$};
\draw[accc, very thick, -Stealth] (3.3, 0.8) -- (5.0, 0.8) node[midway, above, font=\scriptsize, accc] {$+2 \times 6$};
\node[accc, font=\small] at (2.8, 0.4) {$S\!=\!12$};
\draw[accc, very thick, -Stealth] (5.8, 0.8) -- (7.5, 0.8) node[midway, above, font=\scriptsize, accc] {$+1 \times 18$};
\node[accc, font=\small] at (5.3, 0.4) {$S\!=\!24$};
\node[accc, font=\small] at (7.8, 0.4) {$S\!=\!42$};
\foreach \k/\c in {1/2, 2/2, 3/1} {
\node[font=\small, fill=yellow!20, rounded corners, inner sep=2pt] at (\k * 2.5, 0) {代价 $+\c$};
}
\end{tikzpicture}
\caption{询问 $[1, 3]$ 的贪心过程。$S$ 为累积减量（绿色），每一步在当前位置追加操作使 $S \ge b'_k$。}
\label{fig:greedy}
\end{figure}
\section{$O(nq)$ 暴力}
上述贪心直接实现即可得到 $O(nq)$ 的暴力解法。对每个查询 $[l, r]$，先从右向左计算后缀 GCD 数组，再从左到右扫描执行贪心：
\begin{minted}{cpp}
ll reply_to_query(ll l, ll r) {
gcd_ls[r] = aGlo[r];
for (int i = r - 1; i >= l; --i)
gcd_ls[i] = __gcd(gcd_ls[i + 1], aGlo[i]);
ll acc = 0, ans = 0;
for (int i = l; i <= r; ++i) {
if (acc >= bGlo[i]) continue;
ll rem = bGlo[i] - acc;
ll add = (rem + gcd_ls[i] - 1) / gcd_ls[i];
acc += add * gcd_ls[i];
ans += add;
}
return ans;
}
\end{minted}
这段代码的瓶颈在于：每次询问都要逐个扫描 $O(m)$ 个位置。能否加速单次查询？
\section{加速单次查询：后缀 GCD 分块}
暴力中，内层循环逐个扫描 $k = l, l+1, \ldots, r$，而每个位置的 $g_k$ 值可能不同。但仔细观察会发现，$g_k$ 的取值远没有 $O(m)$ 那么多——它最多只有 $O(\log V)$ 种。如果我们按 GCD 值相同的连续段（称为\textbf{块}）来处理，单次查询就只需遍历 $O(\log V)$ 个块，而非 $O(m)$ 个位置。
\subsection{为什么只有 $O(\log V)$ 个块？}
固定右端点 $r$，考虑后缀 GCD $g_k = \gcd(a_k, a_{k+1}, \ldots, a_r)$，其中 $k$ 从 $r$ 到 $1$。
\begin{itemize}
\item $g_r = a_r$。
\item $g_{k-1} = \gcd(a_{k-1}, g_k)$，因此 $g_{k-1} \mid g_k$。
\item 若 $g_{k-1} \neq g_k$，则 $g_{k-1}$ 是 $g_k$ 的\textbf{真因子}，故 $g_{k-1} \le g_k / 2$。
\end{itemize}
从 $g_r \le V$ 出发，每次变化至少减半，最多减半 $\lfloor \log_2 V \rfloor$ 次就到 $1$。因此不同的 $g$ 值最多 $O(\log V)$ 个（$V = \max a_i$），它们构成连续的若干\textbf{块}。
注意这里的界来自"每次变化必须整除且至少减半"，与 $n$ 无关。即使所有 $a_i$ 互素，GCD 也会一步降到 $1$ 并不再变化，块数反而最少。
图~\ref{fig:blocks} 以 $a = [6, 12, 18, 40, 50]$（对应下标 $1 \sim 5$，右端点 $r = 5$）为例展示了分块结构。
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[>=Stealth, scale=1.0]
\foreach \k in {1,...,5} {
\node[font=\small, below] at (\k * 2.2, -0.3) {$k = \k$};
}
\fill[blockbg, rounded corners=3pt] (1*2.2 - 0.7, -0.1) rectangle (3*2.2 + 0.7, 0.7);
\fill[blue!8, rounded corners=3pt] (4*2.2 - 0.7, -0.1) rectangle (4*2.2 + 0.7, 0.7);
\fill[orange!12, rounded corners=3pt] (5*2.2 - 0.7, -0.1) rectangle (5*2.2 + 0.7, 0.7);
\foreach \k/\gv in {1/2, 2/2, 3/2, 4/10, 5/50} {
\node[font=\normalsize, gcdc, font=\bfseries] at (\k * 2.2, 0.3) {$\gv$};
}
\draw[decorate, decoration={brace, amplitude=5pt, mirror}, thick]
(1*2.2 - 0.6, -0.7) -- (3*2.2 + 0.6, -0.7)
node[midway, below=6pt, font=\small] {块 1：$g = 2$};
\draw[decorate, decoration={brace, amplitude=5pt, mirror}, thick]
(4*2.2 - 0.6, -0.7) -- (4*2.2 + 0.6, -0.7)
node[midway, below=6pt, font=\small] {块 2：$g = 10$};
\draw[decorate, decoration={brace, amplitude=5pt, mirror}, thick]
(5*2.2 - 0.6, -0.7) -- (5*2.2 + 0.6, -0.7)
node[midway, below=6pt, font=\small] {块 3：$g = 50$};
\end{tikzpicture}
\caption{$a = [6, 12, 18, 40, 50]$，右端点 $r = 5$ 时后缀 GCD 的分块结构。5 个位置仅产生 3 个 GCD 块。}
\label{fig:blocks}
\end{figure}
\subsection{按块做贪心：单次查询 $O(\log V)$}
有了分块结构，我们重新审视暴力的内层循环。对同一个 GCD 块（值为 $g$，覆盖位置 $[lo, hi]$），$g$ 是定值，而累积减量 $S$ 单调递增。所以块内唯一能触发追加的是 $b'$ 的\textbf{最大值} $M$——追加 $\lceil (M - S) / g \rceil$ 次后 $S \ge M$，块内其余位置自然被满足。
因此，对一个块只需查询 $M = \max(b'_{lo}, \ldots, b'_{hi})$：若 $M \le S$ 则跳过；否则追加并更新 $S$。单次查询只遍历 $O(\log V)$ 个块，每个块 $O(1)$，总共 $O(\log V)$。
对比暴力代码，优化后的单次查询逻辑几乎一一对应：
\begin{minted}{cpp}
// 暴力：逐个位置扫描 // 优化：逐个 GCD 块扫描
for (int i = l; i <= r; ++i) { for (auto &blk : blocks) {
int lo = max(blk.lo, l);
int hi = blk.hi;
if (lo > hi) continue;
if (acc >= bGlo[i]) continue; ll mx = queryMax(lo, hi);
ll rem = bGlo[i] - acc; if (mx > acc) {
ll add = (rem + gcd_ls[i] - 1) ll c = (mx - acc + blk.g - 1)
/ gcd_ls[i]; / blk.g;
acc += add * gcd_ls[i]; acc += c * blk.g;
ans += add; cost += c;
} }
}
\end{minted}
左边用 $b_k$ 判定，右边用块内 $\max b$ 判定；左边用 $g_k$，右边用块的统一 GCD 值。逻辑完全一致，只是粒度从单个位置变成了一整个块。
\subsection{$O(1)$ 区间最大值：ST 表}
按块做贪心需要快速查询任意区间 $[lo, hi]$ 内 $b$ 的最大值。对数组 $b$ 预处理一个 \textbf{ST 表}即可实现 $O(1)$ 查询：
\begin{minted}{cpp}
void buildST() {
LOG = 1;
while ((1 << LOG) <= N) LOG++;
st.assign(LOG, vector<ll>(N + 1));
for (int i = 1; i <= N; i++) st[0][i] = b[i];
for (int j = 1; j < LOG; j++)
for (int i = 1; i + (1 << j) - 1 <= N; i++)
st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
ll queryMax(int l, int r) {
int k = 31 - __builtin_clz(r - l + 1);
return max(st[k][l], st[k][r - (1 << k) + 1]);
}
\end{minted}
\subsection{跨查询复用块列表}
至此，单次查询已经是 $O(\log V)$ 了，但还剩一个问题：对每个查询 $[l, r]$，我们需要拿到右端点为 $r$ 时的 GCD 块列表。如果每次都从头算，又退化回 $O(n)$。
注意到块列表中每个块的值是 $\gcd(a_k, \ldots, a_r)$。当右端点从 $r$ 扩展到 $r + 1$ 时，GCD 的结合律保证：
$$\gcd(a_k, \ldots, a_r, a_{r+1}) = \gcd(\underbrace{\gcd(a_k, \ldots, a_r)}_{\text{已有块的值}},\; a_{r+1})$$
每个已有块只需与 $a_{r+1}$ 做一次 $\gcd$，不用从头重算。而 $\gcd$ 操作只会让值不变或变小，块只会合并不会分裂，所以块数也不会增加（末尾追加的新块至多 $+1$）。
这意味着块列表对右端点具有\textbf{增量可维护性}：推进一步的代价仅为 $O(\log V)$。于是我们将所有询问离线，按右端点 $r$ 分组，从 $r = 1$ 到 $n$ 依次推进块列表，顺便回答所有以当前 $r$ 为右端点的查询。左端点 $l$ 的影响在查询时通过 \texttt{max(blk.lo, l)} 裁剪即可，无需块列表本身感知它。
\begin{minted}{cpp}
vector<Block> blocks;
for (int r = 1; r <= N; r++) {
vector<Block> nb;
for (auto &blk : blocks) {
ll ng = __gcd(blk.g, a[r]);
if (!nb.empty() && nb.back().g == ng)
nb.back().hi = blk.hi;
else
nb.push_back({ng, blk.lo, blk.hi});
}
if (!nb.empty() && nb.back().g == a[r])
nb.back().hi = r;
else
nb.push_back({a[r], r, r});
blocks = move(nb);
// 回答所有右端点为 r 的查询
for (auto [l, id] : queries[r]) {
ll acc = 0, cost = 0;
for (auto &blk : blocks) {
int lo = max(blk.lo, l);
int hi = blk.hi;
if (lo > hi) continue;
ll mx = queryMax(lo, hi);
if (mx > acc) {
ll c = (mx - acc + blk.g - 1) / blk.g;
cost += c;
acc += c * blk.g;
}
}
ans[id] = cost;
}
}
\end{minted}
\section{复杂度分析}
\begin{itemize}
\item \textbf{ST 表预处理}：$O(n \log n)$。
\item \textbf{扫描线维护 GCD 块}：每步更新 $O(\log V)$ 个块，总计 $O(n \log V)$。
\item \textbf{回答查询}：每次查询遍历 $O(\log V)$ 个块，每块 $O(1)$ 查询区间最大值，总计 $O(q \log V)$。
\item \textbf{总时间复杂度}：$O(n \log n + (n + q) \log V)$，其中 $V = \max a_i \le 10^9$，$\log V \approx 30$。
\item \textbf{空间复杂度}：$O(n \log n)$（ST 表）。
\end{itemize}
\section{AC 代码}
\inputminted{cpp}{../src/1009_GCD.cpp}
\end{document}
|
