CSP-S 2026 初赛试题解析（第二部分：阅读程序题（第二题））精讲

第二部分·阅读程序第（2）题：最大公约数与 ST 表

同学们，今天我们要进入一个很有意思的数学与编程冒险：

假如有一排宝箱，每个宝箱里装着一个正整数。探险家可以随时询问：从第 L 个宝箱到第 R 个宝箱，这些数字的最大公约数是多少？

如果只问一次，我们可以慢慢算；可是，如果连续问几万次，每次都从头计算，就可能太慢了。

于是，程序员想出了一个聪明的办法：**提前把许多区间的答案算好，查询时直接取出需要的信息。**这就是本题涉及的 ST 表思想。

不过，在正式讲解前，需要先核对一个重要细节：

试卷第 15 行实际写的是 if (pw[t + 1] > i)，不是 >=。因此，严格按照这份 PDF 的代码，第 27 题应选 C。

在其他网站，试卷将条件改成 pw[t + 1] >= i，那么第 27 题答案就会变成 D。下面会分别说明，避免大家把两种代码混在一起。

一、程序的任务是什么？

程序读入：

• n：数组中有多少个数；

• m：一共要进行多少次查询；

• a[1] 到 a[n]：数组中的数字；

• 每次查询的 L 和 R：要查询的区间左右端点。

例如：

n = 5
a = {4, 2, 6, 3, 9}

如果查询：

L = 2
R = 5

就相当于询问：

2, 6, 3, 9

这几个数字的最大公约数是多少？

我们可以一步步计算：

gcd(2, 6) = 2
gcd(2, 3) = 1
gcd(1, 9) = 1

所以答案是：

1

程序要做的，就是快速完成这样的查询。

二、先认识最大公约数函数 gcd()

试卷中的函数如下：

int gcd(int x, int y) {
if (y == 0) return x;
return gcd(y, x % y);
}

它使用的是辗转相除法。

1. 什么是最大公约数？

例如，数字 12 的因数有：

1, 2, 3, 4, 6, 12

数字 8 的因数有：

1, 2, 4, 8

它们共同的因数是：

1, 2, 4

其中最大的就是 4，因此：

gcd(12,8) = 4

2. 辗转相除法怎么工作？

计算：

gcd(12,8)

可以这样做：

gcd(12, 8)
= gcd(8, 12 % 8)
= gcd(8, 4)
= gcd(4, 8 % 4)
= gcd(4, 0)
= 4

程序的规则是：

• 如果 y == 0，就返回 x；

• 否则，继续计算 gcd(y, x % y)。

可以记住这句口诀：

大数除小数，余数接着算；余数变成零，前一个数就是答案。

三、程序中的 pw[] 是什么？

程序有这样一段代码：

t = 0;
pw[0] = 1;

for (i = 1; i <= 24; i++)
pw[i] = pw[i – 1] * 2;

每次都把前一个数乘以 2。

因此：

所以：

为什么程序要准备这些 2 的幂呢？

因为 ST 表会处理长度为：

1、2、4、8、16、32、64……

的区间。

这些长度都可以写成    。

四、ST 表的核心：dp[i][j]

程序首先执行：

for (i = 1; i <= n; i++)
dp[i][0] = a[i];

因为：

2^0=1

所以 dp[i][0] 表示：

从 a[i] 开始，连续 1 个数的最大公约数。

也就是：

dp[i][0] = a[i];

接着程序建表：

for (j = 1; j <= lg[n]; j++)
for (i = 1; i + pw[j] – 1 <= n; i++) {
dp[i][j] = gcd(
dp[i][j – 1],
dp[i + pw[j – 1]][j – 1]
);
}

我们把这段代码拆开看。

1. dp[i][j] 到底表示什么？

它表示：

从 a[i] 开始，连续 2j2^j 个数的最大公约数。

例如：

因此，第 25 题的正确选项是：

B：从 a[i] 开始连续 2j2^j 个数的最大公约数。

2. 如何从小区间拼出大区间？

假设我们要计算长度为 4 的区间：

a[i], a[i+1], a[i+2], a[i+3]

可以把它拆成两个长度为 2 的区间：

左边：a[i], a[i+1]
右边：a[i+2], a[i+3]

先分别求出两边的最大公约数，再求它们的最大公约数：

dp[i][2] = gcd(dp[i][1], dp[i + 2][1]);

一般情况下：

dp[i][j] = gcd(
dp[i][j – 1],
dp[i + pw[j – 1]][j – 1]
);

这里的 pw[j – 1] 就是    ，表示右半段的起点。

记忆方法：大区间拆成两个一样长的小区间，再用 gcd() 合起来。

五、逐题讲解

第 22 题：区间 [2,5] 的答案是不是 1？

题目给出：

n = 5
a = {4, 2, 6, 3, 9}
L = 2
R = 5

区间 [2,5] 中的数字是：

2, 6, 3, 9

计算：

gcd(2, 6) = 2
gcd(2, 3) = 1
gcd(1, 9) = 1

所以输出确实是 1。

答案：√（对）。

第 23 题：如果区间长度为 1，输出一定等于 a[L] 吗？

当：

L = R

区间长度为：

R−L+1=1

这个区间只有一个数：

a[L]

程序查询时，使用：

lg[R – L + 1]

此时：

lg[1] = 0

因此查询就相当于：

gcd(dp[L][0], dp[L][0])

又因为：

dp[L][0] = a[L];

所以：

gcd(a[L], a[L]) = a[L]

因此输出一定等于 a[L]。

答案：√（对）。

第 24 题：区间最大公约数一定不小于区间最小值吗？

题目说：

任意一次查询的输出结果一定不小于该查询区间内的最小值。

我们用一个反例就能判断。

假设区间中只有：

4, 6

区间最小值是：

4

但：

gcd(4, 6) = 2

显然：

2 < 4 

所以最大公约数可能小于区间最小值。

实际上，正整数的最大公约数是区间中每个数的约数，因此它不会大于区间最小值。

答案：×（错）。

六、第 26 题：建表的时间复杂度

题目询问第 17～22 行建表过程的时间复杂度，并说明一次 gcd() 运算视为 O(1)O(1)。

建表代码的结构是：

for (j = 1; j <= lg[n]; j++)
for (i = 1; i + pw[j] – 1 <= n; i++) {
dp[i][j] = gcd(…);
}

1. 外层循环

j 从 1 到 lg[n]。

而：

因此外层循环大约执行：

O(log⁡n)次。

2. 内层循环

对于每一个 j，i 最多遍历约 n 个位置，因此内层循环是：

O(n)

每次循环只做一次 gcd()，题目已经告诉我们把它看成 O(1)。

所以总复杂度为：

O(nlog⁡n)

选项中对应的是：

B： 。

答案：B。

七、重点讲解第 27 题：lg[x] = 5 时，x 的范围是多少？

这题的关键是理解 lg[] 是如何计算的。

1. 先看我拿到的试卷中代码

试卷第 14～16 行是：

for (i = 1; i <= 100000; i++)
if (pw[t + 1] > i)
lg[i] = t;
else
t++, lg[i] = t;

请特别注意：

pw[t + 1] > i

这里是严格大于号 >。

2. 用边界值跟踪

一开始：

t = 0;

前面已经知道：

pw[1] = 2
pw[2] = 4
pw[3] = 8
pw[4] = 16
pw[5] = 32
pw[6] = 64

当 i = 32

此时 t = 4，所以：

pw[t + 1] = pw[5] = 32;

判断条件是：

32 > 32

这不成立。

于是执行：

t++;
lg[i] = t;

得到：

t = 5
lg[32] = 5

当 i = 33

现在 t = 5：

pw[t + 1] = pw[6] = 64;

判断：

64 > 33

成立。

所以：

lg[33] = 5

当 i = 64

此时仍然是 t = 5：

64 > 64

不成立。

于是 t 增加为 6：

lg[64] = 6

因此，按照 本PDF 中的 >：

lg[x]=5  ⟺  32≤x≤63  

所以试卷原代码对应 C：[32,63]。

3. 那么，有的试卷，条件为  >= 就会得到 D。

如果代码实际是：

if (pw[t + 1] >= i)
lg[i] = t;
else
t++, lg[i] = t;

那么边界会变化。

• i = 32：32 >= 32 成立，因此 lg[32] = 4。

• i = 33：32 >= 33 不成立，t 增加为 5，因此 lg[33] = 5。

• i = 64：64 >= 64 成立，因此 lg[64] = 5。

• i = 65：64 >= 65 不成立，t 增加为 6，因此 lg[65] = 6。

于是：

lg[x]=5  ⟺  33 ≤ x ≤ 64 

这时对应答案就是：

D：[33,64]。

给同学们的边界记忆法

判断条件中的等号很重要！

> 和 >= 只差一个等号，但在临界值处，程序的执行结果就可能不同。

所以本题需要把两件事分清：

因此，要严格按照这份 PDF 讲解，应写 C；

如果你看到的另一份题目代码，如果使用 >=，答案应写 D。

八、整道题的知识点总结

1. 最大公约数

使用辗转相除法：

int gcd(int x, int y) {
if (y == 0) return x;
return gcd(y, x % y);
}

2. ST 表

dp[i][j]

表示从 a[i] 开始，连续 2 ^ j 个数的最大公约数。

大区间可以拆成两个长度相同的小区间，再通过 gcd() 合并。

3. 建表复杂度

4. lg[] 的边界

必须仔细检查代码中的比较符号，尤其是 > 和 >=。

最终答案

按照本文中，上传的 PDF 中第 15 行的真实代码 pw[t + 1] > i：

√、√、×、B、B、C

如果题目代码改成 pw[t + 1] >= i：

√、√、×、B、B、D

这道题最值得学生们记住的，不只是 ST 表，更是一个阅读程序的好习惯：

不要只记结论，要回到代码里检查每一个边界条件。一个等号，就可能决定一道题的答案。