牛客多校第五场 Problem J Heritage of skywalkert
本文最后更新于 1169 天前,其中的信息可能已经有所发展或是发生改变。

内容纲要

题意

链接: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";
    }
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇