1409 : 签到题

NQ的签到题，题意十分简洁明了：
给定一个元素个数为 n 的整型数组
选择 2 个区间，分别求和得到 a, b 且 a > 0, b > 0, 同时，如果其它任意一个区间的和为 e， 则需要满足 min(a, b) ≥ e
再选择 2 个区间， 分别求和得到 c, d 且 c ＜ 0，d ＜ 0， 同时，如果其它任意一个区间的和为 f，则需要满足 max(c, d) ≤ f
数据保证一定可以找到满足条件的 a, b, c, d
最后，输出 a * b 和 c * d 的最大公约数即可。

第一行输入一个整数 n   4 ≤ n ≤ 3000
第二行输入 n 个整数，每个整数的绝对值小于等于 106，且至少存在两个正数，两个负数。

按题目要求找到 a, b, c, d，输出 gcd(a * b, c * d)即可。
为了再次降低难度，下图为本题的其中一种实现方式，出题人保证下述代码只要敲打正确就一定可以运行出正确的结果：
# include <iostream>
# include <vector>
# include <algorithm>

using namespace std;

typedef long long LL;
const int maxn = 3e3 + 5;
int num[maxn];
vector<LL> zhengshu, fushu; // 为了对新生更加友好，这里特意用拼音命名

LL get_sum(int i, int j)
{
    LL sum = 0;
    while (i <= j)
        sum += num[i++];
    return sum;
}

LL gcd(LL a, LL b)
{
    while (b) {
        LL t = b;
        b = a % b;
        a = t;
    }
    return a;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> num[i];
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++) {
            LL x = get_sum(i, j);
            if (x > 0)
                zhengshu.push_back(x);
            else if (x < 0)
                fushu.push_back(x);
        }
    sort(zhengshu.begin(), zhengshu.end());
    sort(fushu.begin(), fushu.end());
    LL a = zhengshu[zhengshu.size() - 1], b = zhengshu[zhengshu.size() - 2];
    LL c = fushu[0], d = fushu[1];
    cout << gcd(a * b, c * d) << endl;
    return 0;
}

6
2 2 -1 -1 2 -1

2

逆乾