第 1 题 与数组相比，链表在（ ）操作上通常具有更高的效率。

A. 随机访问元素

B. 查找指定元素

C. 在已知位置插入或删除节点

D. 遍历所有元素

【答案】C

【考纲知识点】

【解析】

A  数组效率更高

数组通过下标可直接定位元素（时间复杂度 O (1)）；链表必须从头节点依次遍历（时间复杂度 O (n)）。

B  效率无优势

无序情况下，数组和链表都需要从头遍历对比（时间复杂度 O (n)）；有序数组可二分查找，效率远高于链表。

C  正确

数组：插入 / 删除需要将后续所有元素向后 / 向前移动，时间复杂度 O (n)；

链表：仅需修改前后节点的指针指向，无需移动元素，时间复杂度 O (1)，效率远高于数组。

D 效率相同

数组和链表都需要逐个访问所有元素，时间复杂度均为 O (n)。

第 2 题 下面C++代码实现双向链表。函数 is_empty() 判断链表是否为空，如链表为空返回 true ，否则返回false 。横线处不能填写（ ）。

A. return head == nullptr;

B. return tail == nullptr;

C. return head.data == 0;

D. return size == 0;

【答案】C

【考纲知识点】

1、双向链表结构体定义：

（1）Node 是节点结构体，包含数据域 data 和两个指针域 prev（前驱）、next（后继）。

（2）DoubleLink 是链表管理结构体，包含头指针 head、尾指针 tail 和节点数量 size。

（3）构造函数初始化时，head 和 tail 均为 nullptr，size = 0，代表空链表。

2、空链表判断逻辑：

空链表的本质是没有任何节点，因此：

（1）头指针 head 为 nullptr

（2）尾指针 tail 为 nullptr

（3）节点数量 size 为 0

【解析】

A. 合法：空链表时 head 为 nullptr，非空时 head 指向第一个节点，因此可以正确判断空链表。

B. 合法：空链表时 tail 为 nullptr，非空时 tail 指向最后一个节点，因此可以正确判断空链表。

C. 不合法

1、语法错误：head 是指针类型，访问成员应使用 -> 而非 .，正确写法应为 head->data。

2、逻辑错误：即使语法修正，当链表为空时 head 是 nullptr，访问 head->data 会导致空指针解引用，程序崩溃；且节点数据 data 可以是任意值，data == 0 不能代表链表为空。

D. 合法：size 记录节点总数，空链表时 size = 0，非空时 size > 0，因此可以正确判断空链表。

第 3 题 基于上题代码正确的前提下，填入相应代码完善 append() ，用于在双向链表尾部增加新节点，横线上应填写（ ）。

【答案】D

【考纲知识点】

双向链表尾部插入节点的核心要求：

1. 1、原尾节点的 next 指针 指向新节点
2. 2、新节点的 prev 指针指向原尾节点
3. 3、更新链表的 tail 指针，使其指向新节点（新的尾节点）

【解析】

A. × 只完成了原尾节点指向新节点，但未建立新节点到原尾节点的前驱关系，也未更新 tail 指针，链表结构不完整。

B. × 只建立了新节点的前驱关系，但原尾节点的 next 指针仍为 nullptr，未指向新节点，导致链表断裂，且更新 tail 后无法再访问原尾节点。

C. × 顺序错误：先更新 tail 会导致原尾节点丢失；newNode->prev = tail 会让新节点的前驱指向自己，逻辑完全错误。

D. √

tail->next = newNode;：原尾节点的后继指向新节点

newNode->prev = tail;：新节点的前驱指向原尾节点

tail = newNode;：更新尾指针为新节点

完整实现了双向链表的尾部插入，保证了双向指针的正确性

第 4 题 下列C++代码用循环链表解决约瑟夫问题，即假设 n 个人围成一圈，从第一个人开始数，每次数到第 k 个的人就出圈，输出最后留下的那个人的编号。横线上应填写（ ）。

【答案】A

【考纲知识点】

约瑟夫问题的循环链表解法核心步骤：

1. 1、构建循环链表：将 n 个人用链表节点连成环，每个节点保存编号。
2. 2、报数与删除：从起点开始数 k 次，找到要出圈的节点，将其从环中移除并释放内存。
3. 3、指针更新：删除节点后，将指针移动到下一个节点，作为下一轮报数的起点。
4. 4、终止条件：当链表只剩一个节点时（p->next == p），该节点即为最后幸存者。

5. 关键操作逻辑

   在循环链表中删除节点p时，必须遵循以下顺序：

1. 1、先修改前驱指针：让p的前驱节点prev的next指针跳过p，直接指向

1. 2、再释放节点内存：删除p指向的节点（delete p），避免内存泄漏。
2. 3、最后更新指针：将p移动到下一个节点（p = prev->next），作为下一轮报数的起点。

【解析】

A.完全正确：

(1)先让前驱节点跳过待删除节点，保证链表完整。

(2)释放p节点内存。

(3)将p移动到下一个节点，准备下一轮报数。

B. 错误：先delete p会导致p成为野指针，后续访问p->next会引发未定义行为。

C. 错误：同样先释放p导致指针失效，且删除逻辑顺序混乱，无法正确移除节点。

D. 错误：先更新p指针后，p已指向原节点的后继，此时delete p会误删下一个节点，破坏链表结构。

【总结】

循环链表删除节点的标准顺序：

1. 1、前驱节点跳过待删除节点
2. 2、释放待删除节点内存
3. 3、将指针移动到下一个节点

第 5 题 下列C++代码判断一个正整数是否是质数，说法正确的是( )。

A. 代码存在错误，比如5是质数，但因为 5 % 5 余数是0返回了 false

B. finish_number 的值应该是 n / 2 ，当前写法将导致错误

C. 当前 while 循环正确的前提是：所有大于3的质数都符合 6k±1 形式

D. while 循环修改如下，其执行效果和执行时间相同。

【答案】C

【考纲知识点】

质数判断的优化：

• 质数除了 2、3、5 外，都可以表示为 6k±1 的形式（即 6 的倍数加减 1），因为任何整数都可表示为 6k, 6k+1, 6k+2, 6k+3, 6k+4, 6k+5，其中 6k, 6k+2, 6k+4 是偶数，6k+3 是 3 的倍数，都不是质数。
• 只需判断到 √n 即可，因为若 n 有大于 √n 的因数，则必然存在一个小于 √n 的因数。

【解析】

代码逻辑分析：

• 代码先处理了 n ≤ 1（非质数）、n = 2,3,5（质数）的情况。
• 再排除了能被 2、3、5 整除的数。
• 最后从 7 开始，以 4,2 交替步长（即 7,11,13,17,19...，对应 6k+1 和 6k-1）循环判断到 √n+1，这正是利用了 6k±1 的质数规律。

选项分析

• A： 错误。代码第 4 行已单独处理 n == 5 并返回 true，不会执行到第 6 行的取模判断。
• B：错误。finish_number = sqrt(n) + 1是正确的，判断到 √n 即可，无需到 n/2，后者效率更低。
• C：正确。while 循环正是基于 “大于 3 的质数都符合 6k±1 形式” 这一规律，用步长 4,2 交替遍历所有 6k±1 的数。
• D：错误。修改后的 for 循环会从 2 开始逐个判断，执行时间远长于原循环（原循环跳过了 2、3、5 的倍数，次数更少）。

第 6 题 下列C++代码用两种方式求解两个正整数的最大公约数，说法错误的是( )。

A. gcd0() 函数的时间复杂度为O(logn)

B. gcd1() 函数的时间复杂度为O(n)

C. 一般说来， gcd0() 的效率高于 gcd1()

D. gcd1() 中的代码 for (int i = small; i >= 1; --i) 应该修改为 for (int i = small; i > 1; --i)

【答案】D

【考纲知识点】

1、欧几里得算法（gcd0）：

基于 gcd(a,b) = gcd(b, a mod b)，递归实现，时间复杂度为 O(log n)，效率极高。

2、暴力枚举法（gcd1）：

从较小数开始向下枚举，找到第一个能同时整除两数的数，时间复杂度为 O(n)，效率较低。

【解析】

A：正确。gcd0 是欧几里得算法，时间复杂度为对数级别 O (log n)。

B：正确。gcd1 是暴力枚举，最坏情况下循环次数等于较小数的值，时间复杂度为 O (n)。

C：正确。欧几里得算法的对数复杂度远优于暴力枚举的线性复杂度，因此 gcd0 效率更高。

D：错误。原代码 i >= 1 是正确的，因为 1 是所有正整数的公约数。若修改为 i > 1，当两数互质时（如 2 和 3），循环会在 i=1 前结束，无法返回正确的最大公约数 1，导致逻辑错误。

第 7 题 下面的代码用于判断整数n 是否是质数，错误的说法是（ ）。

A. 埃氏筛算法相对于上面的代码效率更高

B. 线性筛算法相对于上面的代码效率更高

C. 上面的代码有很多重复计算，因为不是判断单个数是否为质数，故而导致筛选出连续数中质数的效率不高

D. 相对而言，埃氏筛算法比上面代码以及线性筛算法效率都高

【答案】D

【考纲知识点】

1、单个数质数判断（试除法）：

图中代码是试除法，判断单个整数 n 是否为质数时，只需遍历到 √n 即可，时间复杂度为 O (√n)。

优点：判断单个数时，空间复杂度为 O (1)，实现简单。

缺点：筛选连续多个数（如 1~10000）时，会重复计算，效率很低。

2、埃氏筛法（埃拉托斯特尼筛法）：

用于快速筛选一段连续区间内的所有质数，时间复杂度为 O (n log log n)。

核心思想：从 2 开始，将每个质数的所有倍数标记为合数，最终未被标记的数即为质数。

适合场景：批量获取质数，效率远高于对每个数单独用试除法判断。

3、线性筛法（欧拉筛法）：

是埃氏筛法的优化版，时间复杂度为 O (n)，每个合数只会被其最小的质因子筛去一次，避免了重复标记，效率比埃氏筛法更高。

【解析】

A：正确。埃氏筛法在筛选连续多个质数时，通过一次遍历标记所有合数，避免了对每个数重复做试除法，效率远高于图中代码。

B：正确。线性筛法是埃氏筛法的优化，每个合数仅被筛一次，时间复杂度更低，在批量筛选质数时效率高于试除法。

C：正确。图中代码是针对单个数的试除法，若要筛选 1~N 内所有质数，需要对每个数都执行一次 O (√n) 的判断，存在大量重复计算，效率远低于筛法。

D：错误。线性筛法的时间复杂度 O (n) 低于埃氏筛法的 O (n log log n)，因此线性筛法效率比埃氏筛法更高，该选项中 “埃氏筛算法比线性筛算法效率都高” 的表述是错误的。

总结

• 单个数判断：试除法（图中代码）最直接。
• 批量筛选质数：线性筛法 > 埃氏筛法 > 多次试除法。

第 8 题 唯一分解定理描述了关于正整数的什么性质？

A. 任何正整数都可以表示为两个素数的和。

B. 任何大于1的合数都可以唯一分解为有限个质数的乘积。

C. 两个正整数的最大公约数总是等于它们的最小公倍数除以它们的乘积。

D. 所有素数都是奇数。

【答案】B

【考纲知识点】唯一分解定理（算术基本定理）：任何大于 1 的正整数（合数），都可以唯一分解为有限个质数的乘积，且分解形式在不计顺序的情况下是唯一的。

【解析】

A：×  这是哥德巴赫猜想的内容，不是唯一分解定理。

B：√  准确描述了唯一分解定理的核心性质。

C：×  这是最大公约数与最小公倍数的关系公式（gcd(a,b) * lcm(a,b) = a*b），与唯一分解定理无关。

D：×  2 是素数但为偶数，该表述本身错误，也与唯一分解定理无关。

第 9 题 下面的C++代码，用于求一系列数据中的最大值。有关其算法说法错误的是（ ）。

A. 该算法采用分治算法

B. 该算法是递归实现

C. 该算法采用贪心算法

D. 该算法不是递推算法

【答案】C

【考纲知识点】

分治算法：将问题分解为若干规模更小的子问题，递归求解后合并结果。

递归实现：函数调用自身来解决子问题。

贪心算法：每一步都做出当前最优选择，不考虑全局最优。

递推算法：通过已知状态逐步推导出未知状态，一般用循环实现。

【解析】

代码逻辑分析

代码将数组不断二分，递归求解左右子数组的最大值，最后合并得到全局最大值，这是典型的分治 + 递归实现。

选项解析

A： 正确，代码将数组二分后分别求解，属于分治算法。

B： 正确，find_max_recursive 函数调用自身，是递归实现。

C： 错误，该算法是分治而非贪心，贪心是每一步做局部最优选择，而分治是分解问题后合并结果。

D： 正确，该算法是递归实现，不是递推（递推一般用循环迭代）。

第 10 题 下面的C++代码，用于求一系列数据中的最大值。有关其算法说法错误的是（ ）。

A. 本题 find_max() 函数采用的是迭代算法

B. 本题 find_max() 函数的时间复杂度为O(n)

C. 和上一题的 find_max() 相比，因为没有递归，所以没有栈的创建和销毁开销

D. 本题 find_max() 函数和上⼀题的 find_max() 空间复杂度相同

【答案】D

【考纲知识点】

1、迭代算法：通过循环逐步更新变量，直到得到结果，不涉及函数自身调用。

2、时间复杂度：执行次数与输入规模 n 成正比，记为 O (n)。

3、空间复杂度：

（1）迭代版：仅使用常数级额外空间（max_value），空间复杂度为 O (1)。

（2）递归分治版：递归深度为 O (log n)，需要栈空间存储递归调用，空间复杂度为 O (log n)。

4、递归开销：递归调用会创建和销毁函数栈帧，存在额外开销，迭代则没有。

【解析】

代码逻辑分析

这段 find_max() 是迭代实现：

(1)初始化 max_value 为数组首元素。

(2)遍历数组，逐个比较并更新最大值。

(3)遍历结束后返回最终最大值。

选项解析

A：正确。代码通过 for 循环遍历数组，属于迭代算法。

B：正确。需要遍历数组所有元素，时间复杂度为 O (n)。

C：正确。上一题是递归分治实现，会产生函数调用栈的创建与销毁开销；本题是迭代实现，无此开销。

D：错误。

(1)本题迭代版：额外空间仅为 max_value，空间复杂度 O (1)。

(2)上一题递归分治版：递归深度为 O (log n)，空间复杂度 O (log n)。

(3)两者空间复杂度不同。

第 11 题 下面的 C++ 代码用于在升序数组lst 中查找目标值 target 最后一次出现的位置。相关说法，正确的是（）。

A. 当 lst 中存在重复的 target 时，该函数总能返回最后一个 target 的位置，即便 lst 全由相同元素组成

B. 当 target 小于 lst 中所有元素时，该函数会返回 0

C. 循环条件改为 while (low <= high) 程序执行效果相同，且能提高准确性

D. 将代码中 (low + high + 1) / 2 修改为 (low + high) / 2 效果相同

【答案】A

【考纲知识点】

这是二分查找的变体—— 查找目标值最后一次出现的位置，关键设计点：

1、向上取整的 mid 计算：mid = (low + high + 1) / 2，避免在 low 和 high 相邻时陷入死循环。

2、收缩边界逻辑：

（1）若 lst[mid] <= target：说明最后一次出现的位置在 [mid, high]，所以 low = mid。

（2）若 lst[mid] > target：说明目标在 [low, mid-1]，所以 high = mid - 1。

3、循环终止条件：low < high，最终 low == high 时退出循环，再验证该位置是否为目标值。

【解析】

A： 正确

（1）当数组全为相同元素时，lst[mid] <= target 始终成立，low 会不断右移直到 low == high，最终指向最后一个元素，且验证后返回正确位置。

（2）存在重复 target 时，算法会持续向右收缩边界，锁定最后一次出现的位置。

B： 错误

当 target 小于所有元素时，lst[mid] > target 始终成立，high 会不断左移，最终 low == high == 0，此时 lst[0] != target，函数返回 -1，而非 0。

C： 错误

若循环条件改为 while (low <= high)，会导致死循环：当 low == high 时，mid = low，若 lst[mid] <= target，则 low = mid，循环永远不会终止。

D： 错误

若将 mid 改为 (low + high) / 2（向下取整），当 low 和 high 相邻时（如 low=2, high=3），mid=2，若 lst[mid] <= target，则 low=mid=2，循环条件 low < high 仍成立，会陷入死循环，无法正确收敛。

总结

• 查找最后一次出现的二分查找，必须用向上取整计算 mid，并配合 low < high 的循环条件。

第 12 题 有关下面C++代码的说法，错误的是（ ）。

A. “阶段1”的目标是寻找正整数 n 可能的正完全平方根

B. “阶段2”的目标是如果正整数 n 没有正完全平方根，则在可能产生完全平方根附近寻找带小数点的平方根

C. 代码 check_int = (long long)(result + 0.5) 是检查因浮点误差是否为正完全平方根

D. 阶段2的二分法中 high_d - low_d >= epsilon 不能用于浮点数比较，会进入死循环

【答案】D

【考纲知识点】

这段代码是二分法求平方根，分为两个阶段：

阶段 1（整数二分）：在 [1, n] 中寻找最大的整数 k，满足 k² ≤ n，即找到 n 的整数平方根。若 n 是完全平方数，则直接返回 k。

阶段 2（浮点数二分）：在 [k, k+1] 区间内，用二分法逼近 √n，直到区间精度小于 epsilon，得到小数形式的平方根。

【解析】

A：第一阶段是为了找到 n 的整数平方根

B：第二阶段用浮点数二分逼近平方根

C：代码可以正确求所有正实数的平方根

D：在浮点数二分法中，使用 high_d - low_d >= epsilon 作为循环条件是常见的做法，只要 epsilon 选择合理（大于浮点数的机器精度），就不会导致死循环。说法过于绝对

第 13 题 硬币找零问题中要求找给客户最少的硬币。 coins 存储可用硬币规格，单位为角，假设规格都小于10角，且一定有1角规格。 amount 为要找零的金额，约定必须为1角的整数倍。输出为每种规格及其数量，按规格从大到小输出，如果某种规格不必要，则输出为0。下面是其实现代码，相关说法正确的是（ ）。

A. 上述代码采用贪心算法实现

B. 针对本题具体要求，上述代码总能找到最优解

C. 上述代码采用枚举算法

D. 上述代码采用分治算法

【答案】A

【考纲知识点】

硬币找零问题的贪心算法：

• 核心思想：每次尽可能选用面值最大的硬币，以减少总硬币数量。

【解析】

代码逻辑分析

代码先将硬币按从大到小排序，然后依次取当前最大面额的尽可能多的硬币，直到金额为 0，这是典型的贪心算法实现。

选项解析

A：正确。代码每次选择当前最大面额硬币，是贪心算法。

B：错误。虽然贪心算法在一般硬币找零问题中不一定得到最优解，但题目中并未保证所有情况下最优

C：错误。枚举算法会遍历所有可能组合，本题代码未做遍历，不是枚举。

D：错误。分治算法是将问题分解为子问题求解，本题无分解 - 合并逻辑，不是分治。

第 14 题 关于下述C++代码的快速排序算法，说法错误的是（ ）。

A. 在 randomPartition 函数中，变量 i 的作用是记录大于基准值的元素的边界

B. randomPartition 函数随机选择基准值，可以避免输入数据特定模式导致的最坏情况下时间复杂度 O(n²)

C. 快速排序平均时间复杂度是O(nlogn)

D. 快速排序是稳定排序算法

【答案】D

【考纲知识点】

本题考查  快速排序（随机化版）的底层原理、复杂度及稳定性。

代码功能分析

(1)randomPartition：随机选择基准值（pivot），进行分区操作，将小于等于 pivot 的元素移到左侧，大于 pivot 的移到右侧，并返回 pivot 最终位置。

(2)quickSort：递归地对左右子数组进行快速排序。

(3)关键优化：随机化基准值打破了有序数组的最坏情况。

【解析】

A. 正确：

(1)变量 i 的作用：初始化 i = low - 1，在遍历过程中 i 始终指向  最后一个小于等于基准值（pivot） 的元素的边界。

(2)当循环结束时，i+1 就是基准值应该插入的位置。因此，i 确实是记录大于基准值元素的边界（初始状态）。

B. 正确:

(1)随机化的意义：原始快速排序在面对已排序数组时，每次选最左 / 最右作为基准，会导致划分极度不平衡，时间复杂度退化为 O(n²)。

(2)随机选择基准值（randomPartition）可以打破这种 “有序数据” 的特定模式，使得最坏情况概率极低，从而避免 O(n² ) 的发生。

C. 正确:平均时间复杂度：由于随机化优化，快速排序在平均情况下表现极其优秀。对于随机数据，其划分平衡，递归深度为 O(logn)，每层处理 O(n)，总平均复杂度为 O(nlogn)。

D. 错误：

稳定性定义：稳定排序要求相等元素的相对顺序在排序后保持不变。

快速排序的不稳定性：快速排序是交换类排序。在 swap 操作过程中，会打破相等元素的原始相对位置。

例如：数组 [2a, 2b]，在交换过程中可能变成 [2b, 2a]。

因此，快速排序是不稳定排序，该说法错误。

【总结】

• 快速排序是不稳定排序（但效率极高）。
• 随机化快速排序可以避免 O(n2) 的最坏情况。

【考前速记口诀】

“快排不稳随机好，平均 log 平方糟。”

• 快排：不稳定
• 随机：避免最坏情况
• 平均：O(nlogn)
• 最坏：O(n2)（随机化后很难遇到）

第 15 题 小杨编写了一个如下的高精度除法函数，则横线上应填写的代码为（ ）。

【答案】A

【考纲知识点】

高精度除法的核心逻辑是模拟手工除法：

1. 1、从被除数的高位开始，逐位将数字 “下移” 到当前余数中。
2. 2、用当前余数反复减去除数，记录减法次数作为当前位的商。
3. 3、最终得到商和余数。

【解析】

在这段代码中：

（1）r 代表当前余数，d[0] 是个位，d[1] 是十位，以此类推。

（2）第 57-59 行的循环 for (int j = r.len; j > 0; j--) 作用是将余数整体左移一位（即 r.d[j] = r.d[j-1]），为新一位数字腾出个位位置 r.d[0]。

（3）之后需要将被除数的当前位 a.d[i] 放入余数的个位 r.d[0]，并将余数长度 r.len 加 1。

选项解析

A. 正确：

r.d[0] = a.d[i]：将被除数当前位放入余数的个位（因为前面已经左移，个位是空位）。

r.len++：余数长度增加 1，正确反映新加入一位后的长度。

B. 错误：r.d[i] 不是余数的个位，直接赋值会破坏余数结构，位置错误。

C. 错误：位置错误，且 r.len = 1 会重置长度，丢失之前的余数。

D. 错误：r.len = 1 会重置长度，导致之前的余数被丢弃，逻辑断裂。

【高精度除法 完整执行流程演示】

一、题目：计算 1234 ÷ 56

被除数 a = 1234   除数 b = 56      求：商 和 余数

// 57-59行 余数整体左移一位（给新数字腾个位）for (int j = r.len; j > 0; j--)    r.d[j] = r.d[j-1];r.d[0] = a.d[i];   // 填的空  把当前位放进余数个位r.len++;           // 长度+1

二、一步步模拟运行

我们用数组存储数字：

• d [0] = 个位
• d [1] = 十位
• d [2] = 百位
• d [3] = 千位

所以：

• a = 1234 → d[0]=4, d[1]=3, d[2]=2, d[3]=1

第 1 轮：i=3（取被除数最高位 1）

1. 余数左移一位原来 r 是空 → 左移后还是空

r.d[0] = a.d[3] = 1r.len++ → r.len = 1

现在余数 r = 1

1 < 56 → 不够除，商这一位是 0

第 2 轮：i=2（取下一位 2）

1. 余数左移一位r = [1] → 左移后变成 [ , 1 ]

r.d[0] = a.d[2] = 2r.len++ → r.len = 2

1. 现在余数 r = 12

2. 12 < 56 → 商这一位是 0

第 3 轮：i=1（取下一位 3）

1. 余数左移一位r = 12 → 左移变成 [, 1, 2]

2. r.d[0] = a.d[1] = 3r.len++ → r.len = 3

   减 1 次：123-56=67
3. 减 2 次：67-56=11共减 

1. 现在余数 r = 123

2. 123 ≥ 56

第 4 轮：i=0（取最后一位 4）

1. 余数左移一位r = 11 → 左移变成 [, 1, 1]

r.d[0] = a.d[0] = 4r.len++ → r.len = 3

1. 114 ≥ 56

• 减 1 次：114-56=58共减 1 次→ 商这一位 = 1→ 余数 r = 58

三、最终结果

1234 ÷ 56商 = 21余数 = 58

r.d[0] = a.d[i];r.len++;

【高精度四则运算笔记（考试版）】

一、高精度加法

核心思想

从个位开始逐位相加，处理进位。

BigInt add(BigInt a, BigInt b) {    BigInt c;    int carry = 0;    c.len = max(a.len, b.len);    for (int i = 0; i < c.len; i++) {        c.d[i] = a.d[i] + b.d[i] + carry;        carry = c.d[i] / 10;        c.d[i] %= 10;    }    if (carry > 0) c.d[c.len++] = carry;    return c;}

演示：123 + 456 = 579

记忆口诀

个位加起，满十进一，最后补进位

二、高精度减法

核心思想

先比较大小，保证大数减小数，从个位开始逐位相减，处理借位。

BigInt sub(BigInta, BigIntb) {    BigInt c;    c.len = a.len;    for (int i = 0; i < a.len; i++) {        c.d[i] += a.d[i] - b.d[i];        if (c.d[i] < 0) {            c.d[i] += 10;            c.d[i+1]--; // 借位        }    }    while (c.len > 1 && c.d[c.len-1] == 0) c.len--; // 去前导零    return c;}

记忆口诀

个位减起，不够借一，末尾去零

三、高精度乘法

核心思想

用第 i 位乘第 j 位，结果存在 i+j 位，最后统一处理进位。

BigInt mul(BigInt a, BigInt b) {    BigInt c;    c.len = a.len + b.len;    for (int i = 0; i < a.len; i++)        for (int j = 0; j < b.len; j++)            c.d[i+j] += a.d[i] * b.d[j];    // 处理进位    for (int i = 0; i < c.len-1; i++) {        c.d[i+1] += c.d[i] / 10;        c.d[i] %= 10;    }    while (c.len > 1 && c.d[c.len-1] == 0) c.len--;    return c;}

演示：12 × 34 = 408

记忆口诀

对位相乘，累加 i+j，最后进位去零

核心思想

模拟手工除法：逐位下移被除数，用减法试商。

pair<BigInt, BigInt> div(BigInt a, BigInt b) {    BigInt q, r;    if (compare(a, b) < 0) {        q.len = 1; q.d[0] = 0; r = a;        return {q, r};    }    // 初始化余数为a的前b.len位    r.len = b.len;    for (int i = a.len - 1; i >= a.len - b.len; i--)        r.d[i - (a.len - b.len)] = a.d[i];    // 逐位计算商    for (int i = a.len - b.len; i >= 0; i--) {        // 余数左移一位，腾个位        if (r.len > 1 || r.d[0] != 0) {            for (int j = r.len; j > 0; j--)                r.d[j] = r.d[j-1];        } else {            r.d[0] = a.d[i]; r.len = 1;            continue;        }        // ---------- 你这题的答案 ----------        r.d[0] = a.d[i]; // 新数放个位        r.len++;         // 长度+1        // ---------------------------------        // 试商：用减法算能减几次b        while (compare(r, b) >= 0) {            r = sub(r, b);            q.d[i]++;        }    }    q.len = a.len - b.len + 1;    while (q.len > 1 && q.d[q.len-1] == 0) q.len--;    while (r.len > 1 && r.d[r.len-1] == 0) r.len--;    return {q, r};}

记忆口诀（对应第 15 题）

左移腾个位，新数放 d [0]，长度加一加

四种运算对比表

【高精度算法・考前一页纸速记版】

总纲速记口诀

加减乘，低位起；除法移位来试商；进位借位要处理。

1. 高精度加法 (+)

核心逻辑

1. （1）从个位 (i=0) 开始逐位相加。
2. （2）计算总和 sum = a[i] + b[i] + 进位。
3. （3）当前位 = sum % 10，进位 = sum / 10。
4. （4）循环结束后，若进位不为 0，补到最高位。

int carry = 0;for(int i=0; i<len; i++){    int sum = a.d[i] + b.d[i] + carry;    c.d[i] = sum % 10;    carry = sum / 10;}if(carry) c.d[c.len++] = carry;

考点：只有加法会在最后多补一位（进位）。

2. 高精度减法 (-)

 核心逻辑

1. （1）保证 a > b (compare 函数)，否则结果为负。
2. （2）从个位 (i=0) 开始逐位相减。
3. （3）若当前位不够减，向前一位借 1 当 10。
4. （4）最后去除前导零（保留至少 1 位）。

for(int i=0; i<len; i++){    if(a.d[i] < b.d[i]) { a.d[i+1]--; a.d[i] += 10; } // 借位    c.d[i] = a.d[i] - b.d[i];}while(c.len>1 && !c.d[c.len-1]) c.len--; // 去零

考点：减法必须先判大小，且要处理前导零。

3. 高精度乘法 (*)

核心逻辑

1. （1）错位累加：第 i 位乘第 j 位，结果存在 i+j 位。
2. （2）双重循环累加，最后统一处理进位。
3. （3）去除前导零。

memset(c.d, 0, sizeof(c.d));c.len = a.len + b.len;for(int i=0; i<a.len; i++)    for(int j=0; j<b.len; j++)        c.d[i+j] += a.d[i] * b.d[j];// 统一进位for(int i=0; i<c.len-1; i++){    c.d[i+1] += c.d[i]/10;    c.d[i] %= 10;}

考点：i+j 错位法，不要从低位开始循环。

• 时间复杂度 O(n2)，数据量大时需优化。

核心逻辑

模拟手算：高位到低位，余数左移，试商减法。

1. 1、初始化：取被除数高位初始化余数。
2. 2、逐位计算：
• （1）余数 左移一位 (r.d[j] = r.d[j-1])。
• （2）新位放入 个位 (r.d[0] = a.d[i])。
• （3）长度 +1。
• （4）试商：用减法 sub 反复减去除数，记录次数为商。
3. 3、处理商和余数的前导零。

// 填空代码 A ✅r.d[0] = a.d[i]; // 新数放入个位r.len++;         // 余数长度加1

考点速记：左移腾个位，新数放 d [0]，长度加一。

• 除法是 O(n2)，因为每次试商都要减法。

考前 3 个避坑坑

1. 1、数组存储顺序：永远记住 d [0] 是个位！倒存方便处理进位 / 借位。
2. 2、除法死穴：一定要写 r.len++，不能写 r.len=1，否则会把之前的余数丢了。
3. 3、去零操作：加、减、乘、除最后都要手动去前导零，除非结果本身是 0。

第 1 题 下面C++代码是用欧几里得算法（辗转相除法）求两个正整数的最大公约数， a 大于 b 还是小于 b 都适用。

【答案】√

【考纲知识点】 

欧几里得算法原理：对于两个正整数 a 和 b，它们的最大公约数满足 gcd(a, b) = gcd(b, a % b)，直到 b = 0 时，a 就是最大公约数。

【解析】

1、代码特点：

（1）循环条件 while(b)：当 b 不为 0 时持续迭代。

（2）每次迭代中，用 temp 保存当前 b，然后计算新的 b = a % b，再将 a 更新为原来的 b。

（3）当 b = 0 时循环结束，返回 a。

2、通用性：无论 a > b 还是 a < b 都适用。若 a < b，第一次迭代中 a % b = a，会自动交换为 gcd(b, a)，无需额外判断大小。

3、示例验证

例：gcd(12, 18)

a=12, b=18 → temp=18, b=12%18=12, a=18

a=18, b=12 → temp=12, b=18%12=6, a=12

a=12, b=6 → temp=6, b=12%6=0, a=6

b=0，循环结束，返回 6   正确

第 2 题 假设函数 gcd() 函数能正确求两个正整数的最大公约数，则下面的 lcm() 函数能求相应两数的最小公倍数。

【答案】√

【考纲知识点】 最小公倍数（LCM）求解的数学公式：

两个正整数 a 和 b 的最小公倍数与最大公约数满足关系：

【解析】

1、代码逻辑：利用已实现的 gcd() 函数，直接代入公式计算。

2、注意事项：

（1）若 a 和 b 较大，a * b 可能会超出 int 范围，导致溢出。更安全的写法是 a / gcd(a, b) * b，先除后乘避免溢出。

（2）前提：a 和 b 均为正整数，且 gcd(a, b) 能正确计算。

3、示例验证

例：lcm(12, 18)

gcd(12, 18) = 6

lcm = (12 * 18) / 6 = 36（正确）。

第 3 题 下面的C++代码用于输出每个数对应的质因数列表，输出形如： {5: [5], 6: [2, 3], 7: [7], 8: [2, 2,2]} 。

【答案】×

【考纲知识点】 

1、map与vector容器

（1）map<int, vector<int>>：有序键值对容器，键为int（存储待分解的数字），值为vector<int>（存储该数字的质因数列表）。

（2）vector<int>：动态数组，用于存储可重复的质因数（如 8 的质因数[2,2,2]）。

2、质因数分解（试除法）

（1）从最小质数2开始，用j循环试除当前数k：

（1.1）若k % j == 0，则j是质因数，将其加入质因数列表，并将k除以j（继续分解）。

（1.2）若不能整除，则j++，尝试下一个数。

（2）循环直到k == 1，完成质因数分解。

3、C++11 范围 for 循环

（1）for (auto& p : prime_factor)：遍历map中所有键值对，p.first为数字，p.second为质因数vector。

（2）for (int v : p.second)：遍历质因数vector，逐个输出质因数。

4、输入处理与swap函数

swap(n, m)：交换两个变量值，确保n ≤ m，保证循环i从n到m正向遍历。

【解析】第 12 行语法错误：prime_factor[i] = prime_factor[i] + j;

prime_factor[i]的类型是vector<int>，而j是int，C++ 中vector不支持直接与int做+运算，这行代码会编译报错。

正确写法：使用vector的push_back()方法向尾部添加元素：prime_factor[i].push_back(j);

第 4 题 下面的C++代码实现归并排序。代码在执行时，将输出一次 HERE 字符串，因为merge()函数仅被调用一次。

【答案】×

【考纲知识点】 

1、归并排序（分治法）

分：递归将数组从中间拆分为左右两个子数组，直到子数组长度为 1（left >= right）。

治：递归排序左右子数组。

合：调用merge()函数，将两个已排序的子数组合并为一个有序数组。

2、merge()函数

（1）功能：合并两个有序子数组[left, mid]和[mid+1, right]，存入临时数组temp，再拷贝回原数组。

（2）调用次数：对于长度为n的数组，归并排序会递归拆分出n-1个 “合并” 操作，因此merge()会被调用n-1次（以数组长度为 2 的幂为例，如长度 8，merge()会被调用 7 次）。

3、递归调用关系

mergeSort()中，每次完成左右子数组排序后，都会执行cout << "HERE"并调用merge()，因此HERE的输出次数等于merge()的调用次数。

【解析】

（以长度为 8 的数组为例）

• 1、递归拆分流程：[0-7] → [0-3]、[4-7]→ [0-1]、[2-3]、[4-5]、[6-7]→ 最终拆为 8 个长度为 1 的子数组。
• 2、合并流程：
1. （1）合并[0]与[1] → 输出HERE1 次
2. （2）合并[2]与[3] → 输出HERE2 次
3. （3）合并[0-1]与[2-3] → 输出HERE3 次
4. （4）合并[4]与[5] → 输出HERE4 次
5. （5）合并[6]与[7] → 输出HERE5 次
6. （6）合并[4-5]与[6-7] → 输出HERE6 次
7. （7）合并[0-3]与[4-7] → 输出HERE7 次
• 结论：merge()被调用 7 次，HERE输出 7 次，与题干 “仅输出一次” 的描述矛盾。

第 5 题 归并排序的最好、最坏和平均时间复杂度均为 O(nlogn)。

【答案】√

【考纲知识点】 

1、分治时间复杂度推导

（1）拆分：每次将数组拆为两半，递归深度为logn（以 2 为底）。

（2）合并：每次merge()操作需要遍历所有元素，时间为O(n)。

（3）总复杂度：递归深度 × 每层合并时间 = O(nlogn)。

2、稳定性与复杂度特性

（1）归并排序不依赖于数据初始顺序，无论数据是否有序，拆分与合并步骤都固定，因此最好、最坏、平均复杂度一致。

（2）空间复杂度为O(n)（需要临时数组存储合并结果）。

【解析】归并排序的最好、最坏和平均时间复杂度均为O(nlogn)。

第 6 题 查字典这个小学生必备技能，可以把字典视为一个已排序的数组。假设小杨要查找一个音首字母为 g 的单词，他首先翻到字典约一半的页数，发现该页的首字母是 m ，由于字母表中 g 位于 m 之前，所以排除字典后半部分，查找范围缩小到前半部分；不断重复上述步骤，直至找到首字母为 g 的页码。这种查字典的一系列操作可看作二分查找。

【答案】√

【考纲知识点】 

1、二分查找原理

（1）前提：数据有序（字典按字母顺序排列，可视为有序数组）。

（2）步骤：

（2.1）取查找范围中点，比较中点元素与目标值。

（2.2）若目标值更小，则排除后半部分；若更大，则排除前半部分。

（2.3）重复直到找到目标或范围为空。

2、时间复杂度：O(logn)，每次查找范围减半。

【解析】查字典的操作是典型的二分查找（折半查找）。

第 7 题 求解下图中A点到D点最短路径，其中A到B之间的12可以理解为距离。求解这样的问题常用Dijkstra算法，其思路是通过逐步选择当前距离起点最近的节点来求解非负权重图（如距离不能为负值）单源最短路径的算法。从该算法的描述可以看出，Dijkstra算法是贪心算法。

【答案】√

【考纲知识点】 

1、Dijkstra 算法核心思想

贪心选择：每次从未访问节点中，选择距离起点最近的节点，将其加入已访问集合。

松弛操作：用刚加入的节点，更新其邻接节点到起点的最短距离。

2、适用条件

图的边权重非负（若存在负权边，需用 Bellman-Ford 算法）。

求解单源最短路径（从一个起点到所有其他节点的最短路径）。

【解析】

• 路径：A → B → C → D，总距离 = 12+10+3=25
• 或A → F → E → D，总距离 = 16+2+4=22（更短）
• 或A → G → E → D，总距离 = 14+8+4=26
• 最终最短路径为A → F → E → D，距离为 22。
• Dijkstra 贪心算法求解非负权图单源最短路径

第 8 题 分治算法将原问题可以分解成规模更小的子问题，使得求解问题的难度降低。但由于分治算法需要将问题进行分解，并且需要将多个子问题的解合并为原问题的解，所以分治算法的效率通常比直接求解原问题的效率低。

【答案】×

【考纲知识点】 

1、分治算法思想：将原问题分解为若干规模更小、结构相同的子问题，递归求解子问题后，再合并结果得到原问题的解。

2、效率分析：

（1）典型例子：归并排序、快速排序，时间复杂度为 O(nlogn)，远优于暴力排序的 O(n² )。

（2）分解与合并的开销，远小于子问题规模缩小带来的收益，因此整体效率更高。

（3）只有在极端情况下（如子问题重复计算、分解 / 合并开销极大），分治才可能不如直接求解。

【解析】

第 9 题 函数 puzzle 定义如下，则调用 puzzle(7) 程序会无限递归。

【答案】×

【考纲知识点】 

1、递归终止条件：if (n == 1) return 1; 是唯一出口。

2、考拉兹猜想（3n+1 问题）：

（1）对正整数 n，若为偶数则取 n/2，若为奇数则取 3n+1，最终都会收敛到 1。

（2）目前猜想未被数学证明，但所有测试过的正整数都满足此规律。

【解析】执行流程（puzzle(7)）

流程最终到达 n=1 并结束，不存在无限递归。

第 10 题 如下为线性筛法，用于高效生成素数表，其核心思想是每个合数只被它的最小质因数筛掉一次，时间复杂度为 O(n)。

【答案】√

【考纲知识点】 线性筛法（欧拉筛）的核心是每个合数仅被其最小质因数筛除一次，时间复杂度为 O(n)。

【解析】

1、核心思想：

（1）维护质数列表 primes 和标记数组 is_prime。

（2）遍历 i 从 2 到 n：

（2.1）若 i 是质数，加入 primes。

（2.2）遍历所有已找到的质数 primes[j]，标记 i * primes[j] 为合数。

（2.3）若 i % primes[j] == 0，立即终止内层循环（保证primes[j]是i的最小质因数，从而保证i * primes[j]的最小质因数也是primes[j]）。

2、时间复杂度：O(n)，每个合数仅被筛除一次，无重复操作。

3、与埃氏筛对比：

埃氏筛：同一合数可能被多个质因数多次筛除，时间复杂度 O(nloglogn)。

线性筛：避免重复筛除，效率更高，适合生成大范围内素数。

3.1 编程题 1

试题名称：奖品兑换

时间限制：1.0 s

内存限制：512.0 MB

3.1.1 题目描述

班主任给上课专心听讲、认真完成作业的同学们分别发放了若干张课堂优秀券和作业优秀券。同学们可以使用这两种券找班主任兑换奖品。具体来说，可以使用 a张课堂优秀券和 b张作业优秀券兑换一份奖品，或者使用b 张课堂优秀券和 a张作业优秀券兑换一份奖品。

现在小 A 有 n张课堂优秀券和 m张作业优秀券，他最多能兑换多少份奖品呢？

3.1.2 输入格式

第一行，两个正整数 n，m，分别表示小 A 持有的课堂优秀券和作业优秀券的数量。

第二行，两个正整数 a,b，表示兑换一份奖品所需的两种券的数量。

3.1.3 输出格式

输出共一行，一个整数，表示最多能兑换的奖品份数。

【题目本质】

有两种兑换奖品的方式：

1. 每份奖品需要 a 张课堂券 + b 张作业券
2. 每份奖品需要 b 张课堂券 + a 张作业券

设用第一种方式兑换 x 份，第二种方式兑换 y 份，则约束为：

目标是最大化 x + y。

【考纲知识点】

• （2）特殊处理 a == b 的情况，直接返回 n/a。

【解题思路】

1. 问题建模

• （1）每份奖品有两种兑换方式：(a,b) 和 (b,a)。
• （2）设总份数为 v，若全部用方式 (a,b) 兑换，则需要 v*a 张课堂券、v*b 张作业券。
• （3）若作业券不足（y > m），则将 t 份奖品改为方式 (b,a) 兑换，调整后：
•              课堂券：x = v*a + t*(b-a)
•              作业券：y = v*b - t*(b-a)
• （4）目标：找到最大的 v，使得调整后 x ≤ n 且 y ≤ m。

2. 二分查找流程

1. 2.1、预处理：
• (1)保证 n ≤ m、a ≤ b，避免重复逻辑。
• (2)若 a == b，两种方式等价，直接返回 n/a。
2. 2.2、二分初始化：
• 左边界 l = 0，右边界 r = n（课堂券数量限制了最大份数）。
3. 2.3、二分迭代：
• (1)取 mid = (l + r + 1) >> 1（向上取整，避免死循环）。
• (2)调用 check(mid) 判断 mid 份是否可行。
• (3)可行则尝试更大份数（l = mid），否则尝试更小份数（r = mid - 1）。
4. 2.4、结果输出：最终 r 即为最大可兑换份数。

3. check(v) 函数逻辑

1. 3.1、初始假设全部用 (a,b) 方式兑换：x = v*a，y = v*b。
2. 3.2、若 y > m（作业券不足）：
• （1）计算需要调整的最小份数 t（向上取整）。
• （2）调整 x 和 y，使 y ≤ m。
3. 3.3、验证调整后 x ≤ n 且 y ≤ m，返回结果。

【参考程序】

#include<cstdio>// 输入输出头文件（scanf/printf）#include<algorithm>// 包含 swap 交换函数using namespace std;int n, m, a, b;         // n=课堂券，m=作业券；a,b=两种兑换消耗int l, r;               // 二分查找的左右边界// ===================== 核心判断函数 =====================// 功能：判断 能不能兑换 v 份奖品// 返回 1=能，0=不能// ========================================================intcheck(int v){    // 用 long long 防止 int 溢出（数据大时相乘会爆 int）    long long x, y, t;    // 假设：全部用【第一种方式】兑换 v 份    // 需要 x = v*a 张课堂券，y = v*b 张作业券    x = 1LL * v * a;    y = 1LL * v * b;    // 如果作业券不够（y > 拥有的 m）    if (y > m) {        // 计算：需要把 t 份奖品换成【第二种方式】兑换        // 这里是 C++ 整数向上取整公式        t = (y - m + (b - a) - 1) / (b - a);        // 切换兑换方式后：        // 作业券消耗减少，课堂券消耗增加        y -= t * (b - a);        x += t * (b - a);    }    // 最终检查：两种券都不超过库存就合法    return x <= n && y <= m;}intmain(){    // 1. 输入：n=课堂券总数，m=作业券总数    scanf("%d%d", &n, &m);    // 输入：a,b=两种兑换方案消耗    scanf("%d%d", &a, &b);    // 2. 统一格式：让 n ≤ m，保证代码逻辑简单    if (n > m)        swap(n, m);    // 统一格式：让 a ≤ b，保证计算方向一致    if (a > b)        swap(a, b);    // 3. 特殊情况：a == b，两种兑换方式完全一样    if (a == b) {        // 每份都要 a 张券，最多能换 n/a 份        printf("%d\n", n / a);        return 0;    }    // ===================== 二分查找开始 =====================    // 目标：找最大的 v，能兑换 v 份奖品    l = 0;        // 左边界：最少 0 份    r = n;        // 右边界：最多 n 份（券的数量限制）    // 二分循环（标准写法：找最大可行值）    while (l < r) {        // mid 向上取整，避免死循环        int mid = (l + r + 1) >> 1;        // 判断 mid 份能不能换        if (check(mid))            l = mid;     // 能换，尝试更大        else            r = mid - 1; // 不能换，缩小范围    }    // 循环结束，r 就是答案    printf("%d\n", r);    return 0;}

【样例验证】

预处理后：n=8, m=8, a=1, b=2二分过程：

• l=0, r=8
   → mid=4，check(4) 可行 → l=4
• l=4, r=8
   → mid=6，check(6) 不可行 → r=5
• l=4, r=5
   → mid=5，check(5) 可行 → l=5
• 循环结束，输出 r=5

【复杂度分析】

时间复杂度：O(logn)，二分次数约 30 次，每次 check 为 O(1)。

空间复杂度：O(1)，仅使用常数变量。

【总结】

1. 1、二分查找：猜最多能换几份奖品，从 0 ~ n 快速找最大值。
2. 2、check 函数：先全用第一种方式换，不够就把部分改成第二种方式，最后看券够不够。
3. 3、统一格式：把 n/m、a/b 交换成小在前、大在后，让计算逻辑更简单。

3.2 编程题 2

试题名称：最大公因数

时间限制：1.0 s

内存限制：512.0 MB

【考纲知识点】

1、最大公因数（GCD）性质：

（1）多个数的 GCD 等于其相邻差值的 GCD：

比如 a=[6,9,12,18,30]，i=1：

• 原序列：7,10,13,19,31
• 直接算 GCD：gcd(7,10,13,19,31)=1
• 用公式算：
• 差值：3,3,6,12，总 GCD D=3
• 答案：gcd(6+1=7,3)=1，结果一致！

再比如 i=3：

• 原序列：9,12,15,21,33
• 直接算 GCD：3
• 公式算：gcd(6+3=9,3)=3，结果一致！

• 关键结论：

• 所有 +i 都在做差时被消掉了！
• 后面的差值部分 和 i 无关，可以提前预处理好。

• 排序后差值恒为非负，避免负数对 GCD 计算的干扰，同时不改变最终结果。

【解题思路】

• （2）遍历数组，逐步计算所有相邻差值的总 GCD，记为 g。

【参考程序】

#include<cstdio>// 用于 scanf/printf 输入输出#include<algorithm>// 用于 sort 排序函数using namespace std;const int N = 1e5 + 5;  // 数组最大长度（适配 1e5 数据规模）int n, q, a[N], g;      // n: 数字个数, q: 询问次数, a[N]: 存储原数组, g: 差值序列的总GCD// 自定义最大公因数函数（支持 0 输入）intgcd(int a, int b){    // 若其中一个数为 0，GCD 等于另一个数（递归终止条件）    if (a == 0 || b == 0)        return a + b;    // 欧几里得算法：gcd(a,b) = gcd(b, a%b)    return gcd(b, a % b);}intmain(){    // 1. 读取输入：数字个数 n 和询问次数 q    scanf("%d%d", &n, &q);    // 2. 读取 n 个正整数存入数组 a（下标从 1 开始）    for (int i = 1; i <= n; i++)        scanf("%d", &a[i]);    // 3. 排序数组（保证差值为正，不影响 GCD 结果）    sort(a + 1, a + n + 1);    // 4. 计算所有相邻差值的 GCD，存入 g    g = 0;  // 初始 g=0，gcd(0, x) = x    for (int i = 2; i <= n; i++)        g = gcd(g, a[i] - a[i - 1]);  // 逐步求差值的总 GCD    // 5. 处理 q 次询问    for (int i = 1; i <= q; i++)        // 答案 = gcd(差值总GCD, a[1]+i)        printf("%d\n", gcd(g, a[1] + i));    return 0;}

• （2）i=2: gcd(3,6+2=8)=1
• （3）i=3: gcd(3,6+3=9)=3

• （2）预处理差值 GCD：O(nlogM)（M 为最大差值）
• （3）询问：O(qlogg)
• （4）总复杂度：O(nlogn+qlogg)，可高效处理 n,q≤105 的数据。