寻找数字 题解

题目分析

题目要求判断一个给定的正整数 (a) 能否表示为某个正整数 (b) 的四次方，即 (a = b^4)。如果可以，输出 (b)，否则输出 (-1)。

数据范围：有 (t) 组测试，(1 \le t \le 10^5)，(1 \le a \le 10^8)。注意 (t) 最大可达十万，因此每组数据的运算必须很快。

解题思路

因为 (a) 最大为 (10^8)，所以 (b) 的最大值不会超过 (\sqrt[4]{10^8} = 10^2 = 100)。实际上：

• (100^4 = 10^8)，刚好是上限。
• (99^4 = 96059601 < 10^8)。

因此，可能满足条件的 (b) 只可能在 (1) 到 (100) 之间。对于每一个 (a)，我们可以通过下面两种方法之一来快速判断：

方法一：数学函数

利用数学库中的开方函数：

• 先对 (a) 开两次平方：(\sqrt{a}) 得到 (a) 的平方根，再开一次平方得到四次方根。
• 由于浮点数可能有精度误差，将结果四舍五入取整得到 (b)。
• 验证 (b^4) 是否等于 (a)，若相等则输出 (b)，否则输出 (-1)。

方法二：二分查找（或直接遍历）

因为 (b) 的范围很小（1 到 100），可以直接在程序中预先计算好 ([1, 100]) 中每个数的四次方，或对每组数据二分查找 (b)。不过直接使用数学函数更简洁。

算法说明

以参考代码的方法为例：

1. 读取测试组数 (t)。
2. 对于每一组数据：
   • 读入 (a)。
   • 计算 sqrt(sqrt(a))，得到 double 类型的四次方根。
   • 转换为 int 类型，得到整数 (b)（C++ 中浮点数转整型会直接截断小数部分，相当于向下取整）。
   • 为了安全，检测 (b) 和 (b+1) 两个数，看哪个的四次方等于 (a)（参考代码只检查了 (b)，有一定风险，但通过实际测试发现对于范围内的 (a)，sqrt(sqrt(a)) 的精度足够。不过为了保险，也可以检查一下 (b) 及相邻的数）。
   • 若找到相等的，输出 (b)；否则输出 (-1)。

浮点数精度问题提示：
在 C++ 中，sqrt 返回 double，连续两次开方后，整数的四次方根理论上应该是精确整数，但计算机浮点运算可能产生微小误差（例如某数开方后得到 99.9999999），转成 int 后变成 99，而实际上应该是 100。因此需要验证 (b^4) 是否等于 (a)，如果不等于，再尝试 (b+1) 或使用 round 函数四舍五入。

优化写法（更安全）：

cpp
复制
1int b = round(sqrt(sqrt(a))); // 四舍五入取整
2if (b * b * b * b == a) ...

时间复杂度分析

每组数据仅做常数次数学运算和整型乘法，时间复杂度为 (O(1))。对于 (t \le 10^5) 的数据，整体时间完全可接受，不会超时。

空间复杂度仅为存储变量的 (O(1))。

参考代码

以下是基于题目所给思路改进的稳健代码，使用了 round 进行四舍五入，并增加了对 (b) 结果的验证。

cpp
复制
1#include <iostream>
2#include <cmath>
3using namespace std;
4
5int main() {
6    int t;
7    cin >> t;
8    while (t--) {
9        int a;
10        cin >> a;
11        // 计算四次方根并四舍五入到最近整数
12        int b = round(sqrt(sqrt(a)));
13        // 验证 b 的四次方是否恰好等于 a
14        if (b * b * b * b == a) {
15            cout << b << endl;
16        } else {
17            cout << -1 << endl;
18        }
19    }
20    return 0;
21}

代码解释

1. sqrt(sqrt(a))：先对 (a) 开平方得到平方根，再开平方得到四次方根。
2. round(...)：将结果四舍五入为最接近的整数，避免截断误差。
3. b * b * b * b == a：验证 (b) 的四次方是否等于原数 (a)。由于 (b) 最大为 100，四次方不会超过 int 范围（大约 (2.1\times10^9)），可以安全比较。
4. 根据验证结果输出 (b) 或 (-1)。

这样，无论输入多大（在题目范围内），都能正确且高效地输出结果。