乘法问题 题解

题目分析

小 A 需要将输入的 $n$ 个正整数相乘，如果乘积超过 $10^6$ 则输出 >1000000，否则输出准确的乘积。

题目给出的数据范围是 $n \le 50$，每个数 $a$ 不超过 $100$。理论上最大乘积可能达到 $100^{50}$，这远远超过了 C++ 内置整数类型的表示范围，但我们并不需要真的计算出这个巨大的数字，因为只要乘积一超过 $10^6$，就可以直接输出结果并结束程序。利用这个“提前终止”的技巧，我们可以完全避免大数溢出问题。

解题思路

采用“边乘边判断”的方式：

1. 初始化乘积变量 prod = 1。
2. 依次读入每个数字 a。
3. 判断 prod * a 是否大于 $10^6$：
   • 如果是，直接输出 >1000000 并终止程序。
   • 如果不是，将 prod 更新为 prod * a。
4. 如果所有数字乘完都没有超过阈值，则输出最终的 prod。

这样做的好处是，程序在乘积达到 $10^6$ 的那一刻就会结束，因此 prod 的最大值不会超过 $10^6 \times 100 = 10^8$，使用 long long 类型完全不会溢出。

算法说明

• 数据类型选择：在 C++ 中，int 能表示的最大值约为 $2.1 \times 10^9$，本题中即使全部乘完也不超过 $10^8$，用 int 也是安全的。但一般习惯上会用 long long 来避免潜在风险。
• 提前终止：当发现乘积即将超出阈值时，直接用 return 0; 结束 main 函数，不再处理后续输入。这是处理“判断是否超过某值”问题时的常用技巧，可以节省时间并避免数值溢出。
• 读入与处理：由于我们可以在判断成立时立即终止程序，因此不需要把所有的数先存到数组里，可以一边读入一边处理。

时间复杂度分析

• 最好情况：第一个数就使乘积超过 $10^6$，那么只需要读入一个数并做一次判断，时间复杂度 $O(1)$。
• 最坏情况：全部 $n$ 个数乘完都没有超过阈值，需要遍历所有数，时间复杂度 $O(n)$。
• 空间复杂度：只使用了常数个变量，$O(1)$。

由于 $n \le 50$，即使是最坏情况，运算量也非常小，完全可以满足时间限制。

参考代码

以下为 C++ 实现：

cpp
复制
1#include <iostream>
2using namespace std;
3
4int main() {
5    int n;
6    cin >> n;
7    
8    long long product = 1;          // 乘积初始化为 1
9    
10    for (int i = 0; i < n; ++i) {
11        int a;
12        cin >> a;
13        
14        // 判断乘上 a 之后是否会超过阈值
15        if (product * a > 1000000) {
16            cout << ">1000000" << endl;
17            return 0;               // 直接结束程序
18        }
19        
20        product *= a;               // 更新乘积
21    }
22    
23    // 所有数乘完都没超，输出准确乘积
24    cout << product << endl;
25    return 0;
26}

代码解释

• long long product = 1;：用 long long 存储乘积，保证在阈值之前不会溢出。
• if (product * a > 1000000)：检查乘以当前数后的结果是否超过 $10^6$。这里 product * a 的最大值不超过 $10^8$，所以 long long 完全够用。
• return 0;：一旦超过阈值，输出 >1000000 后直接退出 main 函数，后面的数字无需再读入。
• 最后，如果循环正常结束，说明所有数乘起来都不超过 $10^6$，输出 product 即可。

总结

本题的关键在于理解“不需要算出真实的大乘积，只需要判断是否超过一个阈值”。利用提前终止的技巧，可以大幅简化问题，避免使用高精度运算。这种思路在信息学竞赛中非常常见，遇到类似“判断是否超过某个值”的问题时可以优先考虑。

希望这篇题解能够帮助大家理解其中的技巧，祝学习愉快！