Ryan's WorkSpace
  • 首页
  • 关于我
  1. 首页
  2. C++
  3. 正文

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

2018年08月04日 1520点热度 0人点赞 0条评论

内容纲要

题意

链接: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";
    }
}

相关

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 暂无
最后更新:2018年08月04日

Ryan Lee

如果帮助到你,请点击广告,谢谢!

点赞
< 上一篇
下一篇 >

文章评论

您需要 登录 之后才可以评论

如果帮助到你,请点击广告,谢谢!

用户您好!请先登录!
登录 注册
Social Media
Github: ryanlee2014
标签聚合
Apache Java hustoj GitHub C++ JavaScript php C
友链
Pacolyon
Lucien's blog
Slian's DreamWork
卡拉搜索
  • 0
  • 17,846
  • 6,853
  • 0
广告

COPYRIGHT © 2020 Ryan's WorkSpace. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

登录
注册|忘记密码?