寻找数字

小杨有一个正整数 $a$，小杨想知道是否存在一个正整数 $b$ 满足 $a=b^4$。

输入格式

第一行包含一个正整数 $t$，代表测试数据组数。

对于每组测试数据，第一行包含一个正整数代表 $a$。

输出格式

对于每组测试数据，如果存在满足条件的正整数 $b$，则输出 $b$，否则输出 $-1$。

样例

3
16
81
10

2
3
-1

对于全部数据，保证有 $1\leq t\leq 10^5$，$1\leq a_i\leq 10^8$。

$t \le 10^5$：测试数据一共有 $10^5$ 组，这意味着我们对每组数据的处理必须非常快，最好是 $O(1)$ 或者非常小的常数级别，否则总时间会超时。

$a_i \le 10^8$：这是判断解题方向的关键。因为 $b^4 = a \le 10^8$，我们可以反推一下底数 $b$ 的最大可能范围：$b \le \sqrt[4]{10^8} = 100$。

也就是说，可能的正整数 $b$ 只有 $1$ 到 $100$ 这 100 种可能！

解题思路

面对如此小的 $b$ 范围，通常有两种非常高效的做法：

方法一：直接使用库函数

我们可以利用 math.h 或 cmath 库中的 pow 函数或者双重 sqrt 函数。

• $\sqrt[4]{a} = \sqrt{\sqrt{a}}$，所以可以对 $a$ 开两次平方根。
• 令 $b = \text{round}(\sqrt{\sqrt{a}})$（使用四舍五入避免浮点数精度误差）。
• 最后验证一下 $b^4$ 是否正好等于 $a$。如果是，输出 $b$；否则输出 $-1$。

复杂度：每组数据 $O(1)$，总时间复杂度 $O(t)$，轻松通过。

方法二：打表 / 预处理

因为 $b$ 只有 $1$ 到 $100$，我们可以直接在程序刚开始时，把 $1^4, 2^4, 3^4, \dots, 100^4$ 的值全部算出来，存入一个哈希表（如 std::map 或 std::unordered_map），或者直接用数组/映射记录。

• 预处理：用一个循环，从 $1$ 遍历到 $100$，算出 $b^4$ 并建立 a 到 b 的映射。
• 查询：对于输入的每个 $a$，直接去表里查是否存在。存在就输出对应的 $b$，不存在就输出 $-1$。

复杂度：预处理 $O(100)$ 可忽略不计，每组查询 $O(1)$，总时间复杂度 $O(t)$，且完全没有浮点数精度问题。

算法实现步骤（以预处理法为例）

1. 全局或主函数开头预处理：

   创建一个大小足够或者使用键值对的查找表。用一个循环让 $b$ 从 $1$ 递增到 $100$，计算 $a = b \times b \times b \times b$，并在表中记录 table[a] = b。

2. 读取测试组数：

   读入正整数 $t$，代表接下来的查询次数。

3. 循环处理每组数据：

   启动一个 while(t--) 循环。每次读入一个正整数 $a$。

4. 查表输出结果：

   检查 $a$ 是否在我们的预处理表中。如果存在，输出对应的 $b$；如果不存在，输出 -1。注意每组输出后要换行。

参考代码

这里给出基于打表/预处理思想的 C++ 参考代码。由于输入输出量较大（$10^5$ 级别），建议加上 ios::sync_with_stdio(false); 来加速输入输出。

#include <iostream>
#include <unordered_map>

using namespace std;

// 我们可以用 unordered_map 来存储 a 到 b 的映射
unordered_map<long long, int> fourth_power_map;

// 预处理函数
void precompute() {
    for (long long b = 1; b <= 100; ++b) {
        long long a = b * b * b * b;
        fourth_power_map[a] = b;
    }
}

int main() {
    // 优化输入输出流，防止大数据量下超时
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 1. 初始化预处理表
    precompute();

    int t;
    if (cin >> t) {
        while (t--) {
            long long a;
            cin >> a;

            // 2. 查表判断
            if (fourth_power_map.count(a)) {
                cout << fourth_power_map[a] << "\n";
            } else {
                cout << -1 << "\n";
            }
        }
    }

    return 0;
}

易错点提示

1. 精度问题：如果你选择用 pow(a, 0.25) 直接开方，浮点数运算可能会有微小的误差（例如本来是 $3$，算出来是 $2.999999$ 转换成整数变成了 $2$）。所以必须配合 round() 函数进行四舍五入，并做最后的乘法验证。
2. I/O 超时：$10^5$ 的数据量如果使用 std::endl 会频繁刷新缓冲区导致 TLE，请务必使用 '\n' 换行，并关闭流同步。