题解

思路推导

若 $n>1$，因数 $1$ 和 $n$ 一定存在，所以 $d(n)\ge n+1$。因此当 $d(n)=c\le C$ 时，只需枚举 $n\le C$。

可以在线性筛中同时维护最小质因数幂的和。设当前数中最小质因子 $p$ 的幂为 $p^e$，对应几何和为 $1+p+\cdots+p^e$。扩展一个相同质因子时更新这两项；扩展新质因子时将因数和乘以 $1+p$。这样可在线性时间求出 $1$ 到最大查询值的因数和。

做法

先读入全部查询并令 $C$ 为最大值。用线性筛计算每个 $n\le C$ 的 $d(n)$。按 $n$ 从小到大遍历，若 $d(n)\le C$ 且该值尚未记录，就令答案表在位置 $d(n)$ 记录 $n$。从小到大的顺序保证记录的是最小解。

小规模可逐个尝试 $n$ 并用平方根分解求因数和；中等规模可用调和级数筛，对每个因数给其倍数累加。独立核验程序使用最小质因子表逐个分解整数。

正确性证明

线性筛的乘法更新依据因数和函数在互质数上的乘法性，以及质数幂公式 $d(p^e)=1+p+\cdots+p^e$，故能正确求出每个 $n\le C$ 的因数和。

任何满足 $d(n)=c\le C$ 的解都有 $n\le c\le C$，不会超出枚举范围。答案表按 $n$ 递增时只写入第一次出现的位置，因此写入值恰是所有满足 $d(n)=c$ 的整数中的最小者；从未写入的位置确实无解。故所有输出正确。

复杂度分析

时间复杂度为 $O(C+t)$，空间复杂度为 $O(C)$，其中 $C=\max c_i$。