G2009 [GESP202403 二级] 乘法问题 题解

知识点：循环乘积、溢出控制、分类输出。

解题思路

逐个乘入正整数，把乘积超过1000000的状态截成1000001，最后输出数值或>1000000。

为什么正确

因子均为正数，乘积超过阈值后不会再变小，因此只保留“超限”状态即可。

易错点

必须在中间步骤就限制数值，不能等全部相乘溢出后再比较；阈值本身仍输出数字。

复杂度

时间O(n)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,x;
    long long p=1;
    cin>>n;
    while(n--) {
        cin>>x;
        p=min(1000001LL,p*x);
    }
    if(p>1000000)cout<<">1000000";
    else cout<<p;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用6个自行生成的测试点。