2024 年 6 月 GESP C++ 五级真题解析(迭代 vs 递归、双链表头尾插操作)

第 1 题 下面C++代码用于求斐波那契数列，该数列第1、2项为1，以后各项均是前两项之和。函数fibo()属于( )。

A. 枚举算法

B. 贪心算法

C. 迭代算法

D. 递归算法

【答案】C

【考纲知识点】迭代算法

迭代算法：核心是通过循环（for/while）重复执行一组操作，利用变量的更新逐步推导结果，依赖 “循环 + 状态更新” 实现，不依赖函数自身调用。

递归算法：核心是函数直接 / 间接调用自身，将大问题拆解为规模更小的同类型子问题，必须有明确的终止条件。

枚举算法：核心是逐一列举所有可能的情况，验证是否符合条件（比如遍历所有数找质数）。

贪心算法：核心是每一步都做 “局部最优” 选择，试图通过局部最优得到全局最优（比如找零钱选面额最大的）。

【解析】

为什么是迭代算法？

代码核心逻辑是for 循环：从第 3 项开始，通过循环重复计算 “前两项之和”，并更新变量状态（a、b、next），逐步推导出第 n 项，完全符合迭代算法 “循环 + 状态更新” 的特征。

为什么排除其他选项？

❶ 不是递归：函数没有调用自身，递归版斐波那契应该是 return fibo(n-1) + fibo(n-2)；

❷ 不是枚举：没有逐一列举所有可能情况，而是按规律推导；

❸ 不是贪心：没有 “局部最优选择” 的逻辑，只是按固定规则计算。

第 2 题 下面C++代码用于将输入金额换成最少币种组合方案，其实现算法是( )。

A. 枚举算法

B. 贪心算法

C. 迭代算法

D. 递归算法

【答案】B

【考纲知识点】贪心算法 

【解析】

核心逻辑：从面值最大的硬币（100）开始，尽可能多地使用该面值硬币，然后用剩余金额继续处理下一个较小面值的硬币，直到金额为 0。

贪心体现：每一步都选择 “当前能使用的最大面值硬币”，这是典型的贪心选择。在人民币等标准货币体系下，这种策略可以保证得到最少硬币数的全局最优解。

第 3 题 小杨采用如下双链表结构保存他喜欢的歌曲列表：

【答案】B

【考纲知识点】双链表的查找特性

【解析】

双链表的查找特性：双链表（doubly linked list）虽然支持双向遍历，但它本质上仍然是一种线性存储结构，不支持随机访问。

要查找某个特定元素，必须从链表头（或尾）开始，逐个节点遍历，直到找到目标或遍历结束。

时间复杂度分析：在最坏情况下（目标元素在链表末尾或不存在），需要遍历链表中所有 n 个节点。

因此，该查找操作的时间复杂度为线性时间 O(n)。

第 4 题 小杨想在如上题所述的双向链表中加入一首新歌曲。为了能快速找到该歌曲，他将其作为链表的第一首歌曲，则下面横线上应填入的代码为（ ）。

A. head->next->prev = p;

B. head->next = p;

C. head->prev = p;

D. 触发异常，不能对空指针进行操作。

【答案】C

【考纲知识点】双链表头插操作

【解析】

双链表头插操作：

（1）在双链表头部插入新节点时，需要同时维护  前驱（prev）和后继（next）两个指针。

（2）新节点 p 的 next 指向原头节点 head。

（3）如果原链表不为空（head != nullptr），原头节点 head 的 prev 指针必须指向新节点 p，以保证链表的双向链接正确。

（4）最后更新头指针 head = p。

voidinsert(dl_node *head, string my_song){    p = new dl_node;          // 创建新节点    p->song = my_song;        // 设置节点数据    p->prev = nullptr;        // 新节点作为头节点，前驱为空    p->next = head;           // 新节点的后继指向原头节点    if (head != nullptr) {    // 如果原链表不为空        head->prev = p;       // 原头节点的前驱指向新节点，完成双向链接    }    head = p;                 // 更新头指针为新节点}

核心要点

• 新节点 p 的 next 指向原头节点 A。
• 原头节点 A 的 prev 指向新节点 p，这一步是双向链表完整性的关键。
• 最后更新 head 指针，使其指向新的头节点 p。

【尾插操作指针变化示意图】

区别：

总结

1. （1）尾插的核心是「找尾节点 + 双向绑定」，空链表需单独处理；
2. （2）头插效率更高（O (1)），尾插因遍历链表效率为 O (n)（若维护尾指针可优化为 O (1)）；
3. （3）无论头插 / 尾插，双链表都要保证「前驱 + 后继」指针双向绑定，否则链表结构断裂。

普通尾插需要遍历找尾节点（O (n)），核心优化是额外维护一个尾指针 tail，始终指向链表最后一个节点，插入时直接用 tail 操作，无需遍历，时间复杂度降为 O (1)。

第 5 题 下面是根据欧几里得算法编写的函数，它计算的是 a与b 的（ ）。

A. 最小公倍数

B. 最大公共质因子

C. 最大公约数

D. 最小公共质因子

【答案】C

【考纲知识点】欧几里得算法（辗转相除法）

1、欧几里得算法（辗转相除法）：

这是计算两个正整数最大公约数（Greatest Common Divisor, GCD）的经典算法。

核心原理：对于任意两个正整数 a 和b，它们的最大公约数等于 b 和 a%b 的最大公约数，即 gcd(a,b)=gcd(b,a%b)。

终止条件：当 b=0 时，gcd(a,0)=a，此时 a 即为所求的最大公约数。

【解析】

下面有关说法，错误的是（ ）。

A. 本题的 gcd() 实现为递归方式。

B. 本题的 gcd() 代码量少，更容易理解其辗转相除的思想。

C. 当 a 较大时，本题的 gcd() 实现会多次调用自身，需要较多额外的辅助空间。

D. 当 a较大时，相比上题中的 gcd() 的实现，本题的 gcd() 执行效率更高。

【答案】D

【考纲知识点】欧几里得算法递归版

1、递归与迭代的核心区别：

递归：函数通过调用自身来分解问题，代码简洁，但每次调用都需要在栈上保存上下文，会产生额外的空间开销和函数调用开销。

迭代：通过循环和变量更新来解决问题，没有函数调用的额外开销，空间复杂度为 O(1)，执行效率通常更高。

2、欧几里得算法的两种实现：

迭代版（上一题代码）：使用 while 循环，空间复杂度 O(1)，效率稳定。

递归版（本题代码）：使用三目运算符和函数自调用，代码极简，但空间复杂度为 O(logmin(a,b))，与递归深度成正比。

【解析】错误。递归实现需要频繁的函数调用和栈操作，而迭代实现是直接的循环和变量更新，没有这些额外开销。因此，在 a 较大时，迭代版的执行效率更高。

第 7 题 下述代码实现素数表的线性筛法，筛选出所有小于等于 n 的素数，则横线上应填的代码是( )。

A. for (int j = 0; j < primes.size() && i * primes[j] <= n; j++)

B. for (int j = 0; j <= sqrt(n) && i * primes[j] <= n; j++)

C. for (int j = 0; j <= n; j++)

D. for (int j = 1; j <= sqrt(n); j++)

【答案】A

【考纲知识点】线性筛法（欧拉筛） 

线性筛法（欧拉筛）：

(1)这是一种高效的素数筛法，核心思想是保证每个合数只被其最小的质因子筛去一次，因此时间复杂度为严格的 O(n)。

(2)关键操作：遍历所有数 i，如果 i 是素数，就将其加入素数列表 primes。

遍历所有已筛出的素数 primes[j]，筛去合数 i×primes[j]。

当 i%primes[j]==0 时，停止内层循环，这是保证线性复杂度的核心。

【解析】

1、循环条件分析：

j < primes.size()：确保遍历所有已筛出的素数。

i * primes[j] <= n：防止筛去的数超过题目给定的范围 n，避免数组越界。

第 8 题 上题代码的时间复杂度是（ ）。

【答案】D

【考纲知识点】线性筛法的复杂度特性

【解析】

线性筛法通过 if (i % primes[j] == 0) break; 这行代码，实现了每个合数仅被其最小质因子筛去一次的严格约束：

彻底消除了埃氏筛法中 “一个合数被多个素数重复筛除” 的问题（如 12 不会被 2 和 3 重复筛）；

所有数字（素数 + 合数）都只会被处理一次，因此时间复杂度达到了线性级别。其最核心的数学性质就是时间复杂度为严格的 O(n)，这也是它被称为 “线性筛” 的根本原因。

第 9 题 为了正确实现快速排序，下面横线上的代码应为（ ）。

A. while (i <= mid)

B. while (i < mid)

C. while (i < j)

D. while (i <= j)

【答案】D

【考纲知识点】快速排序分区核心逻辑

【解析】

总结

快速排序双边扫描法的do-while循环，必须以i <= j作为继续条件，确保所有元素完成分区后再终止循环，这是实现正确快速排序的核心细节。

第 10 题 关于分治算法，以下哪个说法正确？

【答案】A

【考纲知识点】分治算法

分治算法（Divide and Conquer）的核心流程是 分 — 治 — 合：

分解（Divide）：将原问题拆分成若干个规模更小、结构相似的子问题。

解决（Conquer）：递归地解决各个子问题。

合并（Combine）：将子问题的结果合并，得到原问题的解。

【解析】

A 正确：完全符合分治算法的定义。

B 错误：归并排序是分治算法的典型应用（分拆数组 + 合并有序序列）。

C 错误：分治算法通常用于解决大规模问题，小规模问题直接求解更快。

D 错误：分治算法的时间复杂度不一定优于 O(nlogn)，例如归并排序是 O(nlogn)，而快速排序平均是 O(nlogn)、最坏 O(n²)。

第 11 题 根据下述二分查找法，在排好序的数组 1，3，6，9，17，31，39，52，61，79，81，90，96 中查找数值82，和82比较的数组元素分别是（ ）。

A. 52, 61, 81, 90

B. 52, 79, 90, 81

C. 39, 79, 90, 81

D. 39, 79, 90

【答案】C

【考纲知识点】二分查找

【解析】

逐步查找过程

第 1 次比较

left = 0, right = 12

mid = (0 + 12) / 2 = 6 → nums[6] = 39

82 > 39 → 调整区间：left = 6 + 1 = 7

第 2 次比较

left = 7, right = 12

mid = (7 + 12) / 2 = 9 → nums[9] = 79

82 > 79 → 调整区间：left = 9 + 1 = 10

第 3 次比较

left = 10, right = 12

mid = (10 + 12) / 2 = 11 → nums[11] = 90

82 < 90 → 调整区间：right = 11 - 1 = 10

第 4 次比较

left = 10, right = 10

mid = (10 + 10) / 2 = 10 → nums[10] = 81

82 > 81 → 调整区间：left = 10 + 1 = 11

此时 left > right，循环结束，查找失败。

比较序列总结

与 82 依次比较的数组元素为：39 → 79 → 90 → 81。

第 12 题 要实现一个高精度减法函数，则下面代码中加划线应该填写的代码为（ ）。

A. a[i + 1]--;

B. a[i]--;

C. b[i + 1]--;

D. b[i]--;

【答案】A

【考纲知识点】高精度减法

本题考查高精度减法的核心逻辑 ——借位操作。高精度减法模拟手工减法的过程，从低位到高位逐位相减：

• 当本位 a[i] < b[i] 时，需要向 高位（i+1 位）借 1，借 1 当 10，加到本位 a[i] 上。
• 借位后，高位的数值需要减 1，即 a[i + 1]--。

【解析】

• 借位的本质是：从高位 “借” 1 个单位到低位，等价于高位减 1、低位加 10。
• 选项 B：a[i]-- 会让本位更小，逻辑错误；
• 选项 C/D：操作对象是 b，借位只发生在被减数 a 内部，因此错误。

第 13 题 设A 和 B是两个长度为n 的有序数组，现将 A 和 B 合并成一个有序数组，归并排序算法在最坏情况下至少要做（ ）次比较。

【答案】C

【考纲知识点】归并排序

归并排序的合并阶段，是将两个有序数组合并为一个有序数组。

【解析】

第 14 题 给定如下函数：

则当 n=7时，函数返回值为（ ）。

A. 0

B. 1

C. 21

D. -11

【答案】D

【考纲知识点】通过递归递推计算

【解析】

从 n=1 开始递推计算：

• fun(1)=1
• fun(2)=2
• fun(3)=fun(1)−fun(2)=1−2=−1
• fun(4)=fun(2)−fun(3)=2−(−1)=3
• fun(5)=fun(3)−fun(4)=−1−3=−4
• fun(6)=fun(4)−fun(5)=3−(−4)=7
• fun(7)=fun(5)−fun(6)=−4−7=−11

第 15 题 给定如下函数（函数功能同上题，增加输出打印）：

则当 n=4时，屏幕上输出序列为（ ）。

A. 4 3 2 1

B. 1 2 3 4

C. 4 2 3 1 2

D. 4 2 3 2 1

【答案】C

【考纲知识点】递归函数的调用顺序与输出时机

【解析】

一步步拆解 fun(4) 的执行流程：

1. 进入 fun(4)

• 打印 4
• 不满足终止条件，执行 fun(2) - fun(3)

2. 进入 fun(2)

• 打印 2
• 满足终止条件 n==2，返回 2

3. 进入 fun(3)

• 打印 3
• 不满足终止条件，执行 fun(1) - fun(2)

4. 进入 fun(1)

• 打印 1
• 满足终止条件 n==1，返回 1

5. 再次进入 fun(2)

• 打印 2
• 满足终止条件 n==2，返回 2
• 按打印顺序，输出的数字依次是：4 → 2 → 3 → 1 → 2，即 4 2 3 1 2。

二、判断题（每题2分，共20分）

第 1 题 如果将双向链表的最后一个结点的下一项指针指向第一个结点，第一个结点的前一项指针指向最后一个结点，则该双向链表构成循环链表。

【答案】√

【考纲知识点】 双向循环链表的定义

【解析】双向链表中，将尾结点的next指向头结点，头结点的prev指向尾结点，就形成了双向循环链表，满足循环链表 “首尾相连” 的核心特征。

第 2 题 数组和链表都是线性表，链表的优点是插入删除不需要移动元素，并且能随机查找。

【答案】×

【考纲知识点】数组与链表的特性对比

【解析】链表插入 / 删除时不需要移动元素（仅修改指针），但不支持随机查找，只能顺序遍历；数组支持随机查找，但插入 / 删除需要移动大量元素。题目中 “能随机查找” 是错误描述。

第 3 题 链表的存储空间物理上可以连续，也可以不连续。

【答案】√

【考纲知识点】 链表的存储结构

【解析】链表通过指针连接结点，结点在内存中可以是连续或不连续的物理地址，只需要通过指针维护逻辑顺序；而数组的存储空间必须是物理连续的。

第 4 题 找出自然数n以内的所有质数，常用算法有埃拉托斯特尼（埃氏）筛法和线性筛法，其中埃氏筛法效率更高。

【答案】×

【考纲知识点】素数筛法效率对比

【解析】

埃氏筛法时间复杂度为 O(nloglogn)，线性筛法（欧拉筛）时间复杂度为严格 O(n)，因此线性筛法效率更高，题目中 “埃氏筛法效率更高” 的描述错误。

第 5 题 唯一分解定理表明任何一个大于1的整数都可以唯一地表示为一系列质数的乘积，即质因数分解是唯一的。

【答案】√

【考纲知识点】算术基本定理（唯一分解定理）

【解析】算术基本定理指出：任何大于 1 的整数，都可以唯一分解为有限个质数的乘积（不考虑因子顺序），即质因数分解在数学上是唯一的。

第 6 题 贪心算法通过每一步选择局部最优解来获得全局最优解，但并不一定能找到最优解。

【答案】√

【考纲知识点】 贪心算法的核心思想

【解析】贪心算法每一步选择局部最优解，期望最终得到全局最优解，但并非所有问题都能保证全局最优（如硬币找零的非标准货币体系），因此 “不一定能找到最优解” 的描述正确。

第 7 题 归并排序和快速排序都采用递归实现，也都是不稳定排序。（ ）

【答案】×

【考纲知识点】 归并排序与快速排序的稳定性

【解析】

一、核心原理（通俗版）

1. 归并排序（Merge Sort）

• 核心思想：「先分后合」的分治策略，把数组拆到最小单元（单个元素），再两两合并成有序数组，最终合并为完整有序数组。
• 通俗比喻：把一堆乱序的扑克牌，先分成单张，再两张一组排好，接着两组合并成四张有序组，直到整副牌有序。
• 核心步骤：
1. 分解：递归将数组从中间拆分为左右两个子数组，直到子数组长度为 1（天然有序）；

1. 合并：从最小的有序子数组开始，两两合并为更大的有序数组，直到合并完所有子数组。

2. 快速排序（Quick Sort）

• 核心思想：「先定基准，再分区」的分治策略，选一个基准值，把数组分成 “小于基准” 和 “大于基准” 的两部分，再递归处理两部分。
• 通俗比喻：选一张扑克牌当基准，把剩下的牌分成 “比它小” 和 “比它大” 的两堆，再对两堆牌重复这个操作。
• 核心步骤：
1. 选基准：选数组中一个元素作为基准值（pivot，常用首 / 尾 / 中间元素）；

1. 分区：遍历数组，把小于基准的放左边，大于基准的放右边，基准归位到最终位置；
2. 递归：对基准左右的子数组重复上述步骤，直到子数组长度为 1。

三、关键补充说明

1. 稳定性的实际影响：

• 若排序数据包含 “值相同但有附加信息” 的元素（如按成绩排序的学生，成绩相同需保留原顺序），需用归并排序；
• 仅排序纯数值且无需保留原顺序，快速排序更高效。

2. 最坏情况规避：

• 快速排序最坏情况（有序数组）可通过「三数取中法选基准」（选首、尾、中间元素的中位数）避免；
• 归并排序无最坏情况，时间复杂度始终稳定。

3. 代码实现特点：

• 归并排序代码重点在「合并函数」，逻辑固定，不易出错；
• 快速排序代码重点在「分区函数」，分区逻辑（单边 / 双边扫描）灵活，易出边界错误。

• 总结

1. 归并排序：稳定、时间固定、需额外空间，适合需要稳定排序或链表场景；
2. 快速排序：不稳定、平均效率更高、原地排序，是常规数组排序的首选（优化后可规避最坏情况）；
3. 两者均基于分治思想，但核心操作（合并 vs 分区）和特性差异显著。

第 8 题 插入排序有时比快速排序时间复杂度更低。

【答案】√

【考纲知识点】 排序算法的时间复杂度场景

【解析】

第 9 题 在进行全国人口普查时，将其分解为对每个省市县乡来进行普查和统计。这是典型的分治策略。

【答案】√

【考纲知识点】 分治算法的应用场景

【解析】分治策略的核心是 “分解问题→解决子问题→合并结果”。全国人口普查分解为各省市县乡普查，符合分治算法的思想。

第 10 题 在下面C++代码中，由于删除了变量 ptr ，因此 ptr 所对应的数据也随之删除，故执行下述代码时，将报错。

【答案】×

【考纲知识点】 C++ 动态内存管理与指针行为

【解析】

三、编程题（每题 25 分，共 50 分）

3.1 编程题 1

试题名称：黑白格

时间限制：1.0 s

内存限制：512.0 MB

3.1.1 题面描述

小杨有一个 n 行 m 列的网格图，其中每个格子要么是白色，要么是黑色。

小杨想知道至少包含 k 个黑色格子的最小子矩形包含了多少个格子。

3.1.2  输入格式

第一行包含三个正整数 n,m,k，含义如题面所示。

之后 n行，每行一个长度为m 的01 串，代表网格图第 i行格子的颜色，如果为 0，则对应格子为白色，否则为黑色。

3.1.3  输出格式

输出一个整数，代表至少包含k 个黑色格子的最小子矩形包含格子的数量，如果不存在则输出0 。

【考纲知识点】一维前缀和、二分查找优化

【解题思路】

整体思路：枚举列边界 + 行维度累计和 + 二分找最小高度

1、预处理行前缀和：

对每行构建一维前缀和，能快速算出任意列区间内的黑色格子数，为后续计算打基础。

2、枚举左右列边界：

遍历所有可能的左列i和右列j，确定矩形的宽度（j-i+1），将二维问题转化为 “固定宽度，找最小高度” 的一维问题。

3、行维度累计和：

对每个列区间[i,j]，按行累加黑色格子数，得到「1~l 行」的累计和数组num。

4、二分找最小高度：

当累计和≥k 时，通过二分查找在num数组中找最小的上边界，使得「下边界 l - 上边界 L」的高度最小，从而得到当前列区间下的最小矩形面积。

5、全局最小面积：

遍历所有列区间，记录所有满足条件的矩形面积的最小值，最终输出结果。

#include<bits/stdc++.h>// 万能头文件，包含所有常用STL和标准库using namespace std;const int N = 110;       // 定义数组最大尺寸（适配题目n,m≤100的约束）int w[N][N];             // 存储原始网格数据（0/1表示白色/黑色格子）int sum[N][N];           // 每行的一维前缀和：sum[i][j]表示第i行前j列的黑色格子总数int n,m;                 // n为行数，m为列数intmain(){    int k;               // 题目要求的最少黑色格子数    cin>>n>>m>>k;        // 输入行数、列数、最少黑色格子数k    // 1. 读取网格数据 + 构建每行的一维前缀和    for(int i=1;i<=n;i++){  // 行从1开始索引（方便前缀和计算）        string s;        cin>>s;            // 读取每行的字符串（如"01111"）        for(int j=1;j<=m;j++){            w[i][j] = s[j-1] - '0';  // 字符转数字（'0'→0，'1'→1）            // 每行前缀和：第i行前j列和 = 前j-1列和 + 当前格子值            sum[i][j] = sum[i][j-1] + w[i][j];        }    }    int ans = 0;  // 存储最终答案（最小矩形面积），初始为0表示未找到    // 2. 枚举所有左右列边界（i为左列，j为右列）    for(int i=1;i<=m;i++){          // 左列边界        for(int j=i;j<=m;j++){      // 右列边界（j≥i，保证宽度有效）            vector<int> num;        // 存储「从第1行到第l行」的黑色格子累计和            int now = 0;            // 累计黑色格子数（按行累加）            // 3. 按行累加，计算当前列区间[i,j]下的累计和            for(int l=1;l<=n;l++){  // l为当前遍历到的行（下边界）                // 计算第l行在列区间[i,j]内的黑色格子数                int tmp = sum[l][j] - sum[l][i-1];                now += tmp;         // 累加至累计和（1~l行的总黑色格子数）                num.push_back(now); // 记录累计和，用于后续二分查找                // 4. 若累计和≥k，尝试找最小高度                if(now >= k){                    // 初始答案：若未初始化，直接赋值（宽度j-i+1 × 高度l）                    if(ans == 0) ans = (j-i+1)*l;                    // 已初始化，取更小面积                    else ans = min(ans, (j-i+1)*l);                    // 5. 二分查找：找最小的上边界，使1~l行 - 1~mid行的和 ≥k                    int L=1, R=l;   // 二分区间[1, l]                    while (L < R){                        int mid = L + R + 1 >> 1;  // 上取整（避免死循环）                        // 若l行累计和 - mid行累计和 ≥k，说明上边界可上移                        if (now - num[mid-1] >= k) L = mid;                        else R = mid - 1;          // 否则上边界下移                    }                    // 验证二分结果，更新最小面积                    if(now - num[L-1] >= k){                        int height = l - L;  // 高度 = 下边界l - 上边界L                        if(ans == 0) ans = (j-i+1)*height;                        else ans = min(ans, (j-i+1)*height);                    }                }            }        }    }    cout<<ans<<"\n";  // 输出最终结果（无满足条件则输出0）    return 0;}

在这段代码里，矩形面积的核心计算公式是：面积 = 宽度 × 高度。其中宽度由枚举的列边界确定，高度由行维度的累计和 + 二分查找确定。

代码中矩形面积计算的核心是：

宽度：由枚举的左右列边界确定，公式 j-i+1；

高度：分初始高度（l）和优化高度（l-L），其中 L 是二分找到的最小上边界；

面积：始终取「宽度 × 高度」的最小值，保证最终结果是全局最小面积。

【核心优化点说明】

1、降维优化：枚举列边界将二维问题降为一维，避免直接枚举所有矩形（O (n²m²)）的高复杂度；

2、二分优化：在累计和数组中二分找最小上边界，将找最小高度的时间从 O (n) 降到 O (logn)，整体复杂度优化为 O (m²nlogn)，适配 n,m≤100 的题目约束。

3.2 编程题 2

试题名称：小杨的幸运数字

时间限制：1.0 s

内存限制：512.0 MB

3.2.1 题面描述

小杨认为他的幸运数字应该恰好有两种不同的质因子，例如， 12=2*2*3的质因子有 2，3，恰好为两种不同的质因子，因此12 是幸运数字，而 30=2*3*5的质因子有 2，3，5，不符合要求，不为幸运数字。

小杨现在有 n个正整数，他想知道每个正整数是否是他的幸运数字。

3.2.2 输入格式

第一行包含一个正整数 n，代表正整数个数。

之后n 行，每行一个正整数。

3.2.3 输出格式

输出 n行，对于每个正整数，如果是幸运数字，输出1 ，否则输出 0。

3.2.4 样例1

【考纲知识点】

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

从 2 到√x 遍历，找到所有能整除 x 的质数，除尽该因子后继续分解剩余部分。

若最后剩余的 x>1，则其本身是一个质因子。

2、去重存储（set 容器）

使用set<int>存储质因子，自动保证元素唯一性，避免重复统计同一个质因子。

最终set的大小即为不同质因子的数量。

3、输入输出处理

批量读取 n 个正整数，对每个数调用质因子分解函数，根据结果输出 1 或 0。

【解题思路】

题目定义：恰好有 2 种不同质因子的正整数是幸运数字。

解题步骤为：

1、质因子分解：对每个输入的正整数，用试除法分解质因子，并统计不同质因子的数量。

2、判断是否为幸运数字：若不同质因子数量 = 2，输出 1；否则输出 0。

详细步骤

1、预处理：无（直接对每个数单独分解质因子）。

2、质因子分解函数calc(x)

（1）初始化set存储质因子。

（2）从 2 到√x 遍历，若 i 是 x 的因子，将 i 加入set，并除尽 x 中所有 i 因子。

（3）若最后 x>1，将 x 加入set（剩余的 x 是质数）。

（4）返回set的大小（即不同质因子个数）。

3、主函数逻辑

读取 n，然后循环读取 n 个正整数。

对每个数调用calc()，根据返回值是否为 2 输出 1 或 0。

#include<bits/stdc++.h>// 包含所有C++标准库和STL容器的万能头文件using namespace std;const int N = 1e5 + 10;  // 数组最大长度（适配题目n≤1e4的约束）// 计算x的不同质因子个数intcalc(int x){    int res = 0;                  // 临时变量（未使用，可删除）    set<int> s;                   // 用set存储不同质因子（自动去重）    // 试除法分解质因子：从2到√x遍历    for (int i = 2; i * i <= x; i++) {        if (x % i == 0) {         // 若i是x的质因子            s.insert(i);          // 将i加入质因子集合            // 除尽所有i因子，避免重复统计            while (x % i == 0) {                x /= i;            }        }    }    // 若最后x>1，说明剩下的x本身是一个质因子    if (x != 1) {        s.insert(x);    }    return (int)s.size();         // 返回不同质因子的数量}int a[N];                         // 存储输入的n个正整数intmain(){    int n;                        // 正整数的个数    cin >> n;                     // 输入n    long long ans = 0;            // 临时变量（未使用，可删除）    int pre = 0;                  // 临时变量（未使用，可删除）    // 遍历n个正整数    for (int i = 1; i <= n; i++) {        cin >> a[i];              // 输入第i个正整数        int x = calc(a[i]);       // 计算其不同质因子个数        if (x == 2) {             // 若恰好有2种不同质因子            cout << "1\n";        // 输出1（是幸运数字）        } else {            cout << "0\n";        // 输出0（不是幸运数字）        }    }    return 0;}