牛客多校第五场 Problem J Heritage of skywalkert

题意

链接：https://www.nowcoder.com/acm/contest/144/J
来源：牛客网

Given n positive integers, for all (i, j) where 1 ≤ i, j ≤ n and i ≠ j, output the maximum value among . means the Lowest Common Multiple.

题解

维护一个size为100的小根堆(优先队列)，这个堆的值是生成数组中前100大的数。考虑到数的随机性质，可以假定这100个数中一定存在最大的数（暴言）
暴力找到这些数的$max(lcm)$

AC代码

#pragma GCC optimize("O3")

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <array>
#include <regex>
#include <queue>

using namespace std;

using ll = unsigned long long;

unsigned A, B, C;

int n;
unsigned x, y, z;

unsigned tang() {

    unsigned t;
    x ^= x << 16;
    x ^= x >> 5;
    x ^= x << 1;
    t = x;
    x = y;
    y = z;
    z = t ^ x ^ y;
    return z;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    int kase = 0;
    int border = 1e2;
    while (T--) {
        priority_queue<unsigned, vector<unsigned>, greater<unsigned>> q;
        cin >> n >> A >> B >> C;
        x = A, y = B, z = C;
        unsigned mx = 0;
        unsigned tmp = tang();
        q.push(tmp);
        for (int i = 1; i < n; ++i) {
            tmp = tang();
            mx = max(mx, tmp);
            if (q.top() < tmp) {
                q.push(tmp);
                if (q.size() > border) {
                    q.pop();
                }
            }
        }

        ll ans = 0;
        vector<unsigned>ele(q.size());
        int cnt = 0;
        while (!q.empty()) {
            ele[cnt++] = q.top();
            q.pop();
        }

        for(int i = 0;i<cnt;++i) {
            for(int j = i;j<cnt;++j) {
                ans = max(1ull * ele[i] / __gcd(ele[i],ele[j]) * ele[j],ans);
            }
        }

        cout << "Case #" << (++kase) << ": " << ans << "\n";
    }
}