大厂真题 / iflytek

科大讯飞 2026-9-6 笔试真题 - 算法岗

证据边界：本文依据公开题解材料整理。原文中部分数学公式在网页抽取时以 SVG 形式保存，文本版无法可靠恢复的变量、约束或表达式不擅自补写；题面与答案应以实际考试页面为准。

本场考试概述

考试时间 ：2026-9-6 考试岗位 ：算法岗 难度评级 ：中等偏难 考点分析 ： 选择题 23 道，深度学习与机器学习占了一半（图 Transformer 位置编码、卷积输出尺寸、目标检测锚框、GBDT、贝叶斯决策、语音合成评价指标），其余分布在高等数学与概率、复杂度与数据结构、C++ 与 Python 语言特性、操作系统和设计模式上。 第一题：排序贪心（简单） 第二题：线性 DP（中等） 第三题：数论与质因数分解（困难） 建议策略 ： 选择题面广但单题不深，语音方向的题（语音合成主观评价指标、HMM 声学建模）是科大讯飞的特色，值得单独准备。 编程题按第一题到第三题依次变难，建议先拿下前两题再攻第三题。第三题在 且多组询问下卡死了朴素试除，考的是 Miller-Rabin 与 Pollard’s rho 这套模板，平时没写过很难现场推出来。

选择题（23道）

1、在图 Transformer 中，为解决缺少序列位置信息的问题，最常用的结构编码方案是（） A. 引入 Laplacian Eigenvectors 作为固定的节点位置编码 B. 采用循环移位的正余弦编码（sinusoidal）与序列模型相同 C. 使用可学习的绝对位置向量，按节点索引填充 D. 将节点度数追加到特征向量末尾 答案 ：A 难度 ：中等 考点 ：深度学习—Transformer 解释 ：图没有天然的节点顺序，序列模型那套按位置索引的编码在图上无意义，因为节点编号是任意的、换个编号就变了另一套编码。图拉普拉斯矩阵的特征向量由图结构本身决定，与编号无关，能把节点在图上的相对位置刻画出来，是图 Transformer 的主流做法。节点度数只是一个标量，远不足以定位节点。 2、极限 的值为（） A. B. C. D. 答案 ：B 难度 ：简单 考点 ：数学—高等数学 解释 ：把 在 处展开成 ，代入分子得 ，除以 后极限为 。用三次洛必达法则也能得到同样结果。 3、某卷积层的输入特征图宽和高均为 ，卷积核大小为 ，stride=1。请分别计算以下两种设置下该层输出特征图的宽：① dilation rate=1、padding=valid；② dilation rate=2、padding=same。 A. 62, 59 B. 64, 59 C. 64, 64 D. 62, 64 答案 ：D 难度 ：中等 考点 ：深度学习—CNN 解释 ：① valid 表示不补零，输出宽为 。② same 的定义就是让输出与输入同尺寸（stride=1 时），框架会按膨胀后的等效核宽 自动补足所需的零，所以输出仍是 。关键在于 same padding 的补零量是随 dilation 变化的，不是固定值。 4、在递归复杂度分析中，递归式 ，每层拆分后子问题总规模保持 。下列答案正确的是（） A. 子问题个数翻倍后总代价抵消为 B. 每次规模减半后保留一支路径，因此为 C. 共有约 层，每层总代价 ，因此为 D. 共有约 层，每层总代价 ，因此为 答案 ：D 难度 ：简单 考点 ：算法—复杂度 解释 ：规模每层减半，从 降到 需要 层。第 层有 个规模为 的子问题，合并代价合计仍是 ，所以总代价为 。C 把层数与每层代价说反了，结论虽对但推导错误。 5、从数字 0-5 中随机不重复选取 5 个数组成一个五位数，则所组成的五位数中有数字 1 和 2 且数字 1 排在数字 2 之前的概率为（） A. 9/50 B. 17/50 C. 3/25 D. 9/25 答案 ：B 难度 ：中等 考点 ：数学—概率论 解释 ：五位数首位不能为 ，总数为 。含 和 的情形按去掉的那个数字分两类：去掉 时全排列 个；去掉 之一时各有 个，合计 。交换 与 是一一对应且不影响首位是否为 ，故恰好一半满足 在 前，概率为 。 6、下列不属于适配器模式的优点的是（） A. 提高了类的复用 B. 对客户端隐藏了接口转换的细节，提高了系统的透明度 C. 可以让接口不兼容但功能适配的类协同工作 D. 一个目标类适配一个适配者类 答案 ：D 难度 ：简单 考点 ：设计模式—适配器模式 解释 ：D 描述的是类适配器的约束而非好处：Java 这类单继承语言中，类适配器一次只能适配一个适配者类，想同时适配多个就必须改用对象适配器。A、B、C 分别对应复用已有类、屏蔽转换细节、打通不兼容接口，都是适配器模式公认的优点。 7、 GBDT(Gradient Boosting Decision Tree) 又叫 MART(Multiple Additive Regression Trees)，是一种迭代的决策树算法，该算法由多棵决策树组成，并由这些决策树给出决策。下列关于 GBDT 的优缺点说法错误的是（） A. 在分布稠密的数据集上比分布稀疏的数据集上表现差 B. 在预测阶段，各棵树的输出可以独立计算后再求和，因此预测速度较快 C. 在超高维稀疏数据上，表现一般比较差 D. GBDT 不需要对输入数据做特殊预处理 答案 ：A 难度 ：中等 考点 ：机器学习—GBDT 解释 ：A 把优劣说反了。GBDT 在稠密的低维数据上泛化能力与表达能力都很强，恰恰是在高维稀疏数据上表现不佳，因为树的分裂依赖特征取值的有效切分点，稀疏特征提供的切分信息太少。这也正是 C 成立的原因。B、D 是树模型的固有特性：训练必须串行但预测可并行求和，且不需要归一化或标准化。 8、在 Python 3 中执行以下程序，输出结果为（）

a = [['1'] * 2] * 3
a[0][1] = "2"
a[1] = []
print(a)

A. [['1','2'],[],['1','2']] B. 其他选项均不正确 C. [['1','2'],[],['1','1']] D. [[],[],[]] 答案 ：A 难度 ：中等 考点 ：Python—可变对象与浅复制 解释 ：[x] * 3 复制的是引用不是对象，所以 的三个元素指向同一个内部列表。a[0][1] = "2" 是原地修改那个共享对象，三行会同时变成 ['1','2']；而 a[1] = [] 是把下标 重新绑定到一个新列表，只影响这一个位置。最终得到 [['1','2'], [], ['1','2']]。 9、关于基于锚框的目标检测算法和无锚框算法，以下说法正确的是（） A. R-CNN、Faster R-CNN 是无锚框的目标检测算法 B. 基于锚框的目标检测方法的训练效率高，不存在训练样本中正负样本失衡问题 C. 无锚框算法的泛化能力比基于锚框算法要强，适用于小目标检测领域 D. 基于锚框算法，通过热力图直接预测图像中各像素属于待检测物体的概率以及物体的边界框信息，然后根据这些信息生产边界框 答案 ：C 难度 ：中等 考点 ：深度学习—目标检测 解释 ：无锚框算法不依赖人工预设的尺度与长宽比，对尺寸分布偏离先验的目标（如小目标）适应性更好，C 正确。Faster R-CNN 的 RPN 正是锚框机制的代表，A 错。锚框会在图上密集铺设候选框，绝大多数是负样本，正负失衡恰恰是它的典型问题，B 错。D 描述的热力图逐像素预测是 CenterNet 这类无锚框方法的做法，安在锚框算法头上是错的。 10、将关键字序列 采用大根堆（最大堆）并以该序列为顺序表初始状态，使用 Floyd 自底向上建堆法构造为堆；对得到的堆做先序遍历（根-左-右）。堆所对应的先序遍历序列可能为（） A. 78, 66, 12, 58, 13, 31, 27, 9, 63, 19 B. 78, 66, 27, 12, 9, 63, 58, 31, 13, 19 C. 78, 66, 12, 27, 9, 63, 58, 13, 31, 19 D. 78, 63, 58, 13, 31, 66, 12, 27, 9, 19 答案 ：B 难度 ：困难 考点 ：算法—数据结构 解释 ：从最后一个非叶节点 向前逐个下沉。 时 不动； 时 与 交换； 时 与 交换； 时 先与 换、再与 换； 时 先与 换、再与 换。最终堆数组为 ，按根-左-右遍历即得 B。 11、Datalog 是一个使用类似 Prolog 方法表示的语言，但是它的语义比 Prolog 却要简单很多。Datalog 的元素是形如 的原子（atom），其中 代表的含义通常是（） A. 一个简单的表达式 B. 一种特定形式的数据流 C. 表示变量或者常量的项 D. 一个断言，能够用于表示一类语句 答案 ：D 难度 ：中等 考点 ：数据库—声明式查询语言 解释 ：原子 中 是谓词（predicate），它对一组项作出断言，语义上对应一张关系表或一条规则的头部，取值为真或假。括号里的 才是表示变量或常量的项，C 说的是它们而不是 。 12、以下 C++ 代码的运行结果是什么（）

#include <iostream>
using namespace std;

void print(char* a) {
    cout << a << endl;
}

int main() {
    const char* a = "Hello world";
    print(static_cast<char*>(a));
    return 0;
}

A. 编译错误 B. 运行错误 C. Hello D. Hello world 答案 ：A 难度 ：中等 考点 ：C++—类型转换 解释 ：static_cast 不能去掉 const 限定，把 const char* 转成 char* 会在编译期直接报错。要去常性只能用 const_cast，但对指向字符串字面量的指针去常后再写入是未定义行为。 13、在 python3 中执行以下程序，输出结果为（）

a = [1, 2]
b = [3, 4, 5]
res = map(lambda x, y: x+y, a, b)
print(list(res))

A. [4,6] B. [4,6,5] C. [1,2,3,4,5] D. 抛出异常 答案 ：A 难度 ：简单 考点 ：Python—内置函数 解释 ：map 接收多个可迭代对象时按最短的那个截断， 只有两个元素，所以只计算 与 ，剩下的 被丢弃，既不补齐也不报错。结果为 [4, 6]。 14、在资源分配图中，表示一个进程的图形是（） A. 框中一个圆 B. 三角形 C. 框 D. 圆圈 答案 ：D 难度 ：入门 考点 ：操作系统—死锁 解释 ：资源分配图约定进程画成圆圈，资源类画成方框，方框内的小圆点表示该类资源的实例个数。选项 A 描述的是带实例的资源结点，不是进程。 15、线性分类器在二维特征空间中表现较差，散点图显示两类呈环形分布。下列判断更合理的是（） A. 环形分布说明标签编码错误，应把两类标签互换后再训练 B. 散点图呈环形时，训练样本数量对边界估计影响较弱 C. 原空间线性边界不足，可用特征映射或非线性分类器 D. 线性分类器参数较少，所以对环形边界更稳健 答案 ：C 难度 ：简单 考点 ：机器学习—线性分类器 解释 ：环形分布意味着两类在原空间线性不可分，一条直线无论怎么放都分不开内环与外环。把数据映射到更高维（如加入 这一维）后即可线性分开，用核方法或非线性分类器同理。互换标签不改变可分性，参数少也不会让线性边界变得能拟合环形。 16、贝叶斯决策是模式识别中非常重要的决策思想。下列选项中，关于贝叶斯决策的描述正确的是（） A. 贝叶斯决策的思想是根据一定概率模型得到样本属于某一类的先验概率，然后根据先验概率的大小进行决策 B. 贝叶斯决策的思想是根据一定概率模型得到样本属于某一类的先验概率，然后根据先验概率的大小与后验概率进行比较再做出决策 C. 贝叶斯决策的思想是根据一定概率模型得到样本属于某一类的后验概率，然后根据后验概率的大小与先验概率进行比较再做出决策 D. 贝叶斯决策的思想是根据一定概率模型得到样本属于某一类的后验概率，然后根据后验概率的大小进行决策 答案 ：D 难度 ：简单 考点 ：机器学习—贝叶斯决策 解释 ：先验概率 与具体样本无关，只按它决策等于不看数据。贝叶斯决策是用贝叶斯公式把先验与类条件概率结合成后验概率 ，再取后验最大的类别，这样才用上了观测 的信息。 17、5 个人排成一行，甲乙不相邻的排法数为（） A. 96 B. 120 C. 48 D. 72 答案 ：D 难度 ：简单 考点 ：数学—概率论 解释 ：用总数减去相邻的情形。全排列共 种；把甲乙捆成一个整体与其余 人共 个元素全排列有 种，捆内甲乙可互换故乘 得 种相邻排法。相减得 。 18、现采用 KMP 算法，对模式串 S 和主串 T 进行匹配，其中 S=”aaaab”，T=”abaaaabca”，设匹配成功过程中进行的字符间比较的次数为 ，规定 与主串长度之比称为匹配效率 ，求这次 KMP 匹配算法的 （） 注：字符串中字符从字符数组 1 号开始存储；每次字符比较均计数，含匹配与不匹配 A. 0.55 B. 0.33 C. 0.89 D. 1 答案 ：C 难度 ：困难 考点 ：算法—字符串匹配 解释 ：S 的 next 数组为 。匹配过程为： 与 比较成功； 与 失配后回退到 再失配，主串右移；此后 到 与 到 连续五次比较全部成功即匹配完成。累计 次，主串长度为 ，故 。 19、32 位系统中，以下 C++ 代码的运行结果是什么？

#include <iostream>
using namespace std;

int main() {
    int a = 5;
    float b;
    cout << sizeof(++a + b);
    cout << a;
    return 0;
}

A. 2 5 B. 4 5 C. 4 6 D. 2 6 答案 ：B 难度 ：中等 考点 ：C++—sizeof 运算符 解释 ：int 与 float 混合运算按整型提升规则转成 float，32 位系统上 sizeof(float) 为 。关键在于 sizeof 的操作数只在编译期做类型推导、运行期并不求值，所以 ++a 从未真正执行， 仍是 。两次输出连起来即 45。 20、下列哪项不是语音合成质量主观评价指标（） A. CMOS B. AB Best C. MOS D. MCD 答案 ：D 难度 ：中等 考点 ：深度学习—语音合成 解释 ：MOS（平均意见分）、CMOS（对比平均意见分）、AB Best（两两偏好测试）都要靠人耳打分或选择，属于主观评价。MCD 是梅尔倒谱失真，由合成语音与参考语音的倒谱系数直接算出，是客观指标，不需要人参与。 21、一般来说，RNN 经常被用于文本翻译等自然语言处理任务，而 CNN 则经常被用于计算机视觉领域。下列关于 RNN 和 CNN 的说法正确的是（） A. CNN 的结构特性决定了它无法被用于自然语言处理任务 B. CNN 和 RNN 的基本训练思路不同，因此适用于不同任务 C. RNN 模型的效果总是强于 CNN 模型 D. RNN 非常适合处理文本序列 答案 ：D 难度 ：简单 考点 ：深度学习—RNN 解释 ：RNN 按时间步递推并携带隐状态，天然匹配文本这类前后有依赖的变长序列，D 正确。TextCNN 用一维卷积做文本分类效果很好，A 错。两者都靠反向传播与梯度下降训练，B 把差异归到训练思路上并不成立。模型优劣取决于任务与数据，不存在一方总是更强，C 错。 22、隐马尔可夫模型用于语音识别时，隐藏状态通常对应声学建模中的哪类对象（） A. 整句识别结果中的词序列概率路径 B. 音素或其细分声学状态及其转移关系 C. 观测到的 MFCC 特征向量序列本身 D. 词典中的完整词条或短语类别 答案 ：B 难度 ：中等 考点 ：机器学习—隐马尔可夫模型 解释 ：HMM 声学模型中，隐藏状态是发音单元的内部状态，通常把每个音素再切成三个状态来刻画起始、稳定、结束的过渡。MFCC 是能直接量到的观测序列，属于观测层而非隐藏层，C 错；词与句子由语言模型和解码网络处理，不是声学 HMM 的隐藏状态。 23、下面是用 keras 描述的一个简单的 MLP，请问一共需要训练多少个参数？

from keras.models import Sequential
from keras.layers import Dense, Dropout

model = Sequential()
model.add(Dense(32, activation='relu', input_dim=100))
model.add(Dropout(0.5))
model.add(Dense(1, activation='sigmoid'))
model.compile(optimizer='rmsprop', loss='binary_crossentropy', metrics=['accuracy'])
model.summary()

A. 3265 B. 3266 C. 3232 D. 3200 答案 ：A 难度 ：简单 考点 ：深度学习—参数量计算 解释 ：全连接层参数量为「输入维 输出维 + 偏置」。第一层为 ，第二层为 ，Dropout 只是训练时随机置零、不含可训练参数，合计 。选项 C 正是漏掉输出层的干扰项。

第 1 题：招待客人的最多人数

题目描述

输入描述

第一行输入两个正整数 ，分别表示天数和食物总量。 第二行输入 个正整数 ，表示每个人每天的食物消耗量。

输出描述

输出一个整数表示答案。

样例1

输入

3 10
2 4 3

输出

2

样例解释

样例2

输入

5 75
1 1 1 1 1

输出

5

题解：排序贪心

题目问题拆解

一共 天，第 个人在第 天到访并住到第 天，住期内每天吃掉 份食物。总食物为 ，可以任意回绝一些人，问最多能接受几个人。 这是一道把决策先化成独立代价、再排序取前缀的贪心题：难点不在实现，而在看出每个人的总花费与接受了谁无关，从而把”选哪些人”退化成”选哪些数”。

算法实现

先算每个人的代价。第 个人从第 天住到第 天，共 天，每天 份，所以总花费为 这个值只由 与 决定，不含任何与其他人有关的项，因此 个人的花费互不干扰，问题变成：从 个正数里选尽量多个，使它们的和不超过 。 再看该选哪些数。枚举子集是 ， 到 时不可行；但目标只数人数、不管花掉多少，所以人数同为 的方案总能换成花费最小的那 个：把已选中最贵的一个换成没被选中且更便宜的人，总花费只减不增，方案依然合法，反复替换即得。 于是把 升序排序，从最便宜的开始逐个累加，装得下就计数加一。 扫到第一个装不下的人时可以直接停：排序后它之后的 都不小于它，前缀和严格递增，当前前缀既已超过 ，更长的前缀只会更大。 小于最小的 时一个人都请不起，循环第一轮就退出，计数保持 。

时空复杂度分析

时间复杂度 ：。瓶颈是排序，求 与累加各只需一趟 扫描； 时总量微乎其微。 空间复杂度 ：，存放 个人的 数组。 Python

## 招待客人的最多人数 - 排序贪心

## 计算每个人从到访日住到第 n 天的总食物消耗
def build_costs(n, a):
    costs = []
    for i in range(n):
        # 第 i+1 个人第 i+1 天来，住到第 n 天，共 n - i 天
        days = n - i
        costs.append(a[i] * days)
    return costs

## 在总消耗不超过 m 的前提下，最多能接受几个人
def max_guests(costs, m):
    # 答案只关心"接受几个人"，不关心接受谁，所以永远优先挑最便宜的
    costs.sort()
    total = 0
    cnt = 0
    for c in costs:
        # 一旦装不下当前这个最便宜的人，后面的更贵，直接停
        if total + c > m:
            break
        total += c
        cnt += 1
    return cnt

n, m = map(int, input().split())
a = list(map(int, input().split()))
print(max_guests(build_costs(n, a), m))

第 2 题：密码强度的字符串方案数

题目描述

你正在研究密码强度。 给你一个数字 ，让你构造一个长度为 的字符串，要求只能含有小写字母并且构造出的字符串不能含有超过三个连续一样的字符，例如 aaaa、bbbb 等就不符合要求，而 aaabaaa 就符合要求。 现在给你这个 ，问你能构造出多少满足要求的字符串。由于答案可能很大，请将答案对 取模后输出。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下： 在一行上输入一个整数 ，表示字符串长度。

输出描述

对于每一组测试数据，新起一行输出一个整数，表示满足要求的字符串数量。

样例1

输入

2
2
4

输出

676
456950

样例解释 对于第一组测试数据， 为 的时候所有情况均满足要求，故答案为 。 对于第二组测试数据， 为 的时候，总方案数为 。不符合要求的字符串是那些含有 个连续相同字符的子串。在长度为 的字符串中，这只可能是 aaaa、bbbb、、zzzz 这 种情况。因此答案为 。

题解：线性 DP

题目问题拆解

统计长度为 的小写字母串中，不含 个及以上连续相同字符的串有多少个，答案对 取模，共有 组询问。 这是一道状态里要记住”结尾连了几个”的计数 DP 题：转移本身不难，难点在于 与 同为 ，逐组重算会超时，必须让所有询问共用一次递推。

算法实现

朴素做法是对每组询问各递推一次，单次 ， 组合计 ，两者同时顶格时是 次运算，四种语言都过不去。答案只与 有关、与询问的先后无关，所以先把询问全部读进来，只递推到其中最大的 ，之后每组 查表。 状态方程定义 ： 设 表示长度为 、结尾一段相同字符恰好连续 个的方案数。合法串的结尾游程至多为 ，故 只取 三个值就覆盖了全部情况。 状态方程初始化 ： ，其余状态为 。长度为 的串结尾游程只能是 ， 个字母各算一种。 状态方程转移 ： 第一式是新字符与前一个不同：前一位处在哪个状态都能接，新字符从剩下的 个字母里挑，游程重新从 数起。后两式是新字符与前一个相同：游程加长一节，只能由游程少 的状态转来。 连的限制不必额外扣除，它由 没有同字符出路来落实： 再接一个相同字符就凑够 个，转移式里根本不写这一项，非法串自始至终没被计入。 长度为 的答案是三个状态之和 ，每步取模。

时空复杂度分析

时间复杂度 ：，其中 为全部询问里最大的 。瓶颈是那一趟递推，每个 只做常数次乘加；读入与查表各 。，总量在千万次以内。 空间复杂度 ：，三条状态数组与一条答案数组。 Python

## 密码强度的字符串方案数 - 线性 DP

MOD = 10 ** 9 + 7


def build_answers(maxn):
    """f[j][i]：长度为 i、结尾一段相同字符恰好连续 j 个（j=1,2,3）的方案数。
    返回 res[i] = 长度 i 的合法串总数，多组询问共用这张表。"""
    f = [[0] * (maxn + 1) for _ in range(4)]
    res = [0] * (maxn + 1)
    # 长度为 1 时结尾游程必然是 1，26 个字母各算一种
    f[1][1] = 26 % MOD
    res[1] = f[1][1]
    for i in range(2, maxn + 1):
        # 新字符与前一个不同：前一位是什么结尾状态都行，换成另外 25 个字母之一
        f[1][i] = 25 * (f[1][i - 1] + f[2][i - 1] + f[3][i - 1]) % MOD
        # 新字符与前一个相同：结尾游程加长一节，所以只能由长度小 1 的状态转来
        f[2][i] = f[1][i - 1]
        # 游程到 3 就封顶，f[3] 再接同字符就是 4 连，直接不转移，天然满足限制
        f[3][i] = f[2][i - 1]
        res[i] = (f[1][i] + f[2][i] + f[3][i]) % MOD
    return res


## 先把全部询问读进来，才能只预处理到实际用到的最大长度
t = int(input())
queries = [int(input()) for _ in range(t)]
answers = build_answers(max(queries))
## 表建好后每组询问只是一次下标访问，逐行输出即可
for n in queries:
    print(answers[n])

第 3 题：最小奇数质因数

题目描述

给定 个正整数 ，请找出 的最小奇数质因数。如果不存在这样的因数，则输出 。

输入描述

第一行输入一个整数 ，表示测试用例数量。 接下来的 行，每行输入一个整数 。

输出描述

对于每个测试用例，在一行上输出一个整数，表示 的最小奇数质因数；如果 没有大于 的奇数因数，则输出 。

样例1

输入

3
15
2
49

输出

3
-1
7

题解：Miller-Rabin + Pollard’s rho

题目问题拆解

给定 个不超过 的整数 ，对每个 求它最小的奇数质因数； 形如 时没有奇因数，输出 。 这是一道被数据范围逼着换算法的分解题：做法只有”分解质因数后取最小的奇质因子”一句，难点全在 达 、 达 时怎么在时限内分解完。

算法实现

先把因子 剥干净。 反复除以 得到奇数 ， 的质因子全是奇数，答案就是 的最小质因子； 说明 是 的幂，输出 。 朴素做法是从 起逐个奇数试除 ，上界 ， 时合计约 次取模，Python 与 Java 都过不去。卡点在于 是大质数、或两个约 的质数之积时，试除要走满整个区间才出结果。 绕开的办法是不顺序找因子，而是把 完全分解，再取结果里的最小值。分解要用两件工具。 判一个数 是不是质数，用 Miller-Rabin。依据有两条： 为质数时费马小定理给出 ，且方程 只有 两个解。 把 写成 （ 为奇数），从 出发连续平方 次恰好得到 。沿这条链检查，若中途冒出一个不等于 却平方成 的数，就找到了 的第三个平方根， 必是合数。取 这 个底数时判定在 内是确定性的，不会误判。 从合数 里劈出一个非平凡因子（既不是 也不是 的因子），用 Pollard’s rho。造一列伪随机数 ，设 的最小质因子为 ，这列数模 只有 种取值，由生日悖论约 步就会出现重复。 重复意味着有两项满足 却 。此时 同时整除 与 ，于是 找这一对不必两两比较：慢指针每次走一步、快指针走两步，两者在环上必定相遇。 退化成 说明这轮 选得不巧，换一个重来。 量级关键在于合数的最小质因子满足 ，故 ， 时只要约三千步。 两者串成栈式流程：栈里初始只有 ，每次弹出 ，判素为真就收进候选，为假就用 rho 劈成 与 压回；栈空时候选里的最小值即答案。 是大质数时一次判素就结束，不进 rho； 这类 的幂剥完只剩 ，第一步就返回 。

时空复杂度分析

时间复杂度 ：。瓶颈在 rho 撞环的 步，每步一次 带一个 ；Miller-Rabin 是 个底数各做 次模乘，量级远小于 rho。比试除的 快约三个数量级。 空间复杂度 ：，栈中至多存下分解链上的常数级个待分解数。 Python

## 最小奇数质因数 - Miller-Rabin + Pollard's rho
from random import randrange
from math import gcd

## 这 12 个底数对 2^64 以内的数是确定性的，不会误判，所以不用随机底数
BASES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)

## 说明：Python 整数是任意精度的，x * x 到 1e28 也不会溢出，
## 所以不像 C++/Java/Go 那样需要单独写一个模乘函数，直接写 x * x % n 即可


def is_prime(n):
    # Miller-Rabin 素性判定：这 12 个底数对 2^64 以内的数是确定性的，不会误判，
    # 因此不存在概率性出错，判一次就是定论
    if n < 2:
        return False
    # 底数本身必须先特判：n 恰好等于某个底数时快速幂的底会被模成 0，反而判错
    for b in BASES:
        if n % b == 0:
            return n == b  # 能被小底数整除的合数在这里就出局
    # 把 n-1 拆成 d * 2^r，d 为奇数。判定依据是"模素数意义下 1 的平方根只能是 ±1"，
    # 要沿着 a^d, a^2d, a^4d ... 一路平方回到 a^(n-1)，检查中途有没有冒出别的平方根
    d = n - 1
    r = 0
    while d % 2 == 0:
        d //= 2
        r += 1  # r 记录抽出了几个因子 2，也就是后面要连续平方几次
    for b in BASES:
        # 内置 pow 三参形式就是快速幂，指数接近 1e14 时逐次相乘会超时
        x = pow(b, d, n)
        # 起点已经是 ±1，整条链此后恒为 1，这个底数给不出反例，换下一个
        if x == 1 or x == n - 1:
            continue
        witness = True  # 先假设该底数能证明 n 是合数，下面找反例
        # 连续平方 r-1 次，中途出现 n-1 说明这个底数不能证伪
        for _ in range(r - 1):
            x = x * x % n
            if x == n - 1:
                witness = False
                break
        # 全程没出现 n-1，等于找到了 1 的非平凡平方根，n 必是合数
        if witness:
            return False
    return True


def pollard(n):
    # Pollard's rho：用伪随机序列 x -> x^2 + c 找出 n 的一个非平凡因子。
    # 1e14 要试除到 1e7 才安全，多组询问必超时；rho 期望只需 n^(1/4) 步
    if n % 2 == 0:
        return 2  # 偶数直接返回因子 2，省掉一整轮随机游走
    while True:
        # c 决定这条伪随机序列的形状，失败时换 c 就等于换一条轨迹重试
        c = randrange(1, n)
        x = randrange(0, n)
        y = x
        d = 1
        # 龟兔赛跑：慢指针走一步、快指针走两步，两者之差与 n 的 gcd 就是候选因子。
        # 序列在模 n 的某个质因子 p 下会更早成环，那一刻 x≡y (mod p) 但 x≠y (mod n)，
        # gcd(|x-y|, n) 于是恰好把 p 这一侧劈出来
        while d == 1:
            x = (x * x + c) % n
            y = (y * y + c) % n
            y = (y * y + c) % n
            d = gcd(abs(x - y), n)
        # d == n 说明快慢指针在模 n 下同时成环，这轮参数 c 没劈出东西，换个 c 重来
        if d != n:
            return d


def min_odd_prime(n):
    # 先除尽 2，再把剩下的奇数完全分解，取最小质因子
    # 剥掉全部因子 2：题目只要奇质因数，留着 2 会让下面的最小值恒等于 2
    while n % 2 == 0:
        n //= 2
    if n == 1:
        return -1  # 剥完只剩 1，说明 n 是 2 的幂，没有大于 1 的奇因数
    best = n  # n 自身若是质数就是答案，先拿它兜底
    # 用显式栈代替递归分解，既避免深度过大爆栈，也方便随时把半成品因子塞回去
    stack = [n]
    while stack:
        v = stack.pop()
        if v == 1:
            continue  # 1 不含质因子，跳过
        if is_prime(v):
            best = min(best, v)  # 只有质数才有资格更新答案
            continue
        # 合数就劈成两半继续分解，直到栈里只剩质数
        d = pollard(v)
        stack.append(d)
        stack.append(v // d)
    return best


## 第一行是询问组数，之后每行一个待分解的正整数
t = int(input())
for _ in range(t):
    print(min_odd_prime(int(input())))