22.1 数学性质判断问题

“在编程中，我们经常需要判断数字是否具有特定的数学性质，”我微笑着解释道，”今天我们将从一个判断完全四次方数的问题开始。”

22.1.1 寻找数字

题目描述：小杨有一个正整数a，小杨想知道是否存在一个正整数b满足a=b⁴。如果存在，输出b的值；如果不存在，输出-1。

样例输入：

2
16
15

样例输出：

2
-1

代码实现（方法一：暴力枚举）：

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;                   // 读取测试用例数量
    while(t--) {                // 循环处理每个测试用例
        int a;
        cin >> a;               // 读取要判断的正整数a
        bool f = false;         // 标记是否找到符合条件的b
        for(int i = 1; i <= a; i++) {  // 尝试从1到a的每个数字
            if(i * i * i * i == a) {   // 判断i的四次方是否等于a
                cout << i << endl;     // 如果找到，输出i并标记
                f = true;
                break;                 // 找到后立即跳出循环
            }
            if(i * i * i * i > a) break;  // 如果i的四次方已经大于a，后续不需检查
        }
        if(f == false) cout << -1 << endl;  // 如果未找到，输出-1
    }
    return 0;
}

代码实现（方法二：数学优化）：

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int t;
    cin >> t;                   // 读取测试用例数量
    while(t--) {                // 循环处理每个测试用例
        int a;
        cin >> a;               // 读取要判断的正整数a
        int b = sqrt(a);        // 计算a的平方根，相当于a^(1/2)
        int c = sqrt(b);        // 计算b的平方根，相当于a^(1/4)，即a的四次方根
        if(c * c * c * c == a) cout << c << endl;  // 验证c的四次方是否等于a
        else cout << -1 << endl;                    // 不等于则输出-1
    }
    return 0;
}

思考：

• 方法一通过直接枚举1到a的数，检查它们的四次方是否等于a
• 方法二利用数学知识：b = ⁴√a = √√a，大大减少了计算量
• 方法二的时间复杂度为O(1)，而方法一的时间复杂度为O(√a)
• 这个实验展示了数学知识在优化算法中的重要作用

22.1.2 乘法问题

题目描述：小A最初刚刚学习了乘法，为了帮助他练习，我们给他若干个正整数，并要求他将这些数乘起来。对于大部分题目，小A可以精确地算出答案，不过，若这些数的乘积超过10⁶，小A就不会做了。请你写一个程序，告诉我们小A会如何作答。

样例输入：

3
10 100 1000

样例输出：

>1000000

代码实现：

#include <iostream>
using namespace std;

int main() {
    const int N = 1e6;  // 定义限制值10^6
    int n;
    cin >> n;           // 读取数字的数量
    long long cj = 1;   // 用long long类型存储乘积，避免溢出
    while(n--) {        // 循环处理每个数字
        int x;
        cin >> x;        // 读取一个数字
        cj *= x;         // 计算累积乘积
        if(cj > N) {     // 如果乘积超过限制值
            printf(">%d", N);  // 输出">1000000"
            return 0;           // 终止程序
        }
    }
    cout << cj;          // 如果乘积未超过限制值，输出实际乘积
    return 0;
}

思考：

• 使用long long类型存储乘积，避免中间结果溢出
• 每次乘法后立即检查是否超过限制值，及时输出结果
• 这个实验展示了如何处理有限制条件的计算问题
• 注意数据类型的选择对于处理大数值计算的重要性