{"id":379,"date":"2018-08-04T13:26:31","date_gmt":"2018-08-04T13:26:31","guid":{"rendered":"https:\/\/www.haoyuan.info\/?p=379"},"modified":"2018-08-04T17:33:06","modified_gmt":"2018-08-04T17:33:06","slug":"%e7%89%9b%e5%ae%a2%e5%a4%9a%e6%a0%a1%e7%ac%ac%e4%ba%94%e5%9c%ba-problem-j-heritage-of-skywalkert","status":"publish","type":"post","link":"https:\/\/haoyuan.info\/?p=379","title":{"rendered":"\u725b\u5ba2\u591a\u6821\u7b2c\u4e94\u573a Problem J Heritage of skywalkert"},"content":{"rendered":"

\u9898\u610f<\/h2>\n

\u94fe\u63a5\uff1ahttps:\/\/www.nowcoder.com\/acm\/contest\/144\/J
\n\u6765\u6e90\uff1a\u725b\u5ba2\u7f51<\/p>\n

Given n positive integers, for all (i, j) where 1 \u2264 i, j \u2264 n and i \u2260 j, output the maximum value among . means the Lowest Common Multiple.<\/p>\n

\u9898\u89e3<\/h2>\n

\u7ef4\u62a4\u4e00\u4e2asize\u4e3a100\u7684\u5c0f\u6839\u5806(\u4f18\u5148\u961f\u5217)\uff0c\u8fd9\u4e2a\u5806\u7684\u503c\u662f\u751f\u6210\u6570\u7ec4\u4e2d\u524d100\u5927\u7684\u6570\u3002\u8003\u8651\u5230\u6570\u7684\u968f\u673a\u6027\u8d28\uff0c\u53ef\u4ee5\u5047\u5b9a\u8fd9100\u4e2a\u6570\u4e2d\u4e00\u5b9a\u5b58\u5728\u6700\u5927\u7684\u6570\uff08\u66b4\u8a00\uff09
\n\u66b4\u529b\u627e\u5230\u8fd9\u4e9b\u6570\u7684$max(lcm)$<\/p>\n

AC\u4ee3\u7801<\/h2>\n
#pragma GCC optimize(\"O3\")\n\n#include <iostream>\n#include <algorithm>\n#include <cstring>\n#include <vector>\n#include <array>\n#include <regex>\n#include <queue>\n\nusing namespace std;\n\nusing ll = unsigned long long;\n\nunsigned A, B, C;\n\nint n;\nunsigned x, y, z;\n\nunsigned tang() {\n\n    unsigned t;\n    x ^= x << 16;\n    x ^= x >> 5;\n    x ^= x << 1;\n    t = x;\n    x = y;\n    y = z;\n    z = t ^ x ^ y;\n    return z;\n}\n\n\nint main() {\n    ios::sync_with_stdio(false);\n    cin.tie(0);\n    cout.tie(0);\n    int T;\n    cin >> T;\n    int kase = 0;\n    int border = 1e2;\n    while (T--) {\n        priority_queue<unsigned, vector<unsigned>, greater<unsigned>> q;\n        cin >> n >> A >> B >> C;\n        x = A, y = B, z = C;\n        unsigned mx = 0;\n        unsigned tmp = tang();\n        q.push(tmp);\n        for (int i = 1; i < n; ++i) {\n            tmp = tang();\n            mx = max(mx, tmp);\n            if (q.top() < tmp) {\n                q.push(tmp);\n                if (q.size() > border) {\n                    q.pop();\n                }\n            }\n        }\n\n        ll ans = 0;\n        vector<unsigned>ele(q.size());\n        int cnt = 0;\n        while (!q.empty()) {\n            ele[cnt++] = q.top();\n            q.pop();\n        }\n\n        for(int i = 0;i<cnt;++i) {\n            for(int j = i;j<cnt;++j) {\n                ans = max(1ull * ele[i] \/ __gcd(ele[i],ele[j]) * ele[j],ans);\n            }\n        }\n\n        cout << \"Case #\" << (++kase) << \": \" << ans << \"\\n\";\n    }\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u610f \u94fe\u63a5\uff1ahttps:\/\/www.nowcoder.com\/acm\/contest\/144\/J \u6765\u6e90\uff1a\u725b\u5ba2\u7f51 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":"","footnotes":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false},"categories":[39,49,22,45],"tags":[],"class_list":["post-379","post","type-post","status-publish","format-standard","hentry","category-c","category-49","category-22","category-45"],"jetpack_featured_media_url":"","jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p8UC2c-67","jetpack_likes_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/379","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=379"}],"version-history":[{"count":1,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/379\/revisions"}],"predecessor-version":[{"id":380,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/379\/revisions\/380"}],"wp:attachment":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=379"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=379"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=379"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}