{"id":250,"date":"2023-07-08T15:20:29","date_gmt":"2023-07-08T07:20:29","guid":{"rendered":"https:\/\/solost.cn\/?p=250"},"modified":"2023-07-08T15:20:29","modified_gmt":"2023-07-08T07:20:29","slug":"378","status":"publish","type":"post","link":"https:\/\/solost.cn\/?p=250","title":{"rendered":"Codeforces Round 883 (Div. 3) – E2. Rudolf and Snowflakes (hard version)"},"content":{"rendered":"

\u9898\u76ee\u94fe\u63a5<\/h2>\n

\u94fe\u63a5<\/a><\/p>\n

\u9898\u76ee\u5927\u610f<\/h2>\n

\u95ee\u6709\u6ca1\u6709\u751f\u6210\u7684\u96ea\u82b1\u8282\u70b9\u6570\u7b49\u4e8en?\u96ea\u82b1\u662f\u521a\u5f00\u59cb\u662f\u4e00\u4e2a\u70b9\uff0c\u540e\u9762\u4ece\u4e00\u4e2a\u70b9\u8fde\u63a5K\u4e2a\u8282\u70b9\uff0c\u518d\u4ecek\u4e2a\u8282\u70b9\u518d\u8fde\u63a5K\u4e2a\u70b9\uff0ceasy\u7248\u672c\u662fn<=1e6,hard version\u662fn<=1e18<\/p>\n

\u9898\u89e3<\/h2>\n

easy\u7248\u672c\u66b4\u529b\u5373\u53ef\uff0c\u76f4\u63a5\u9884\u5904\u7406\u51fa\u6240\u6709\u7684\u60c5\u51b5\uff0c\u521a\u5f00\u59cb\u96ea\u82b1\u8282\u70b9\u6570\u76ee\u662f\uff0c1 + k + k ^2\uff0c\u7136\u540e\u6bcf\u6b21\u52a0K^i\uff0chard version\u4e0d\u80fd\u8fd9\u6837\u5199\uff0c\u56e0\u4e3a\u65f6\u95f4\u590d\u6742\u5ea6\u592a\u9ad8\u4e86\uff0c\u6240\u4ee5\u6211\u4eec\u4f7f\u7528\u4e8c\u5206\u641c\u7d22\uff0cint\u662f2^32\uff0c\u7ea6\u4e3a10\u4f4d\uff0clong long 64\u4f4d\uff0c\u7ea6\u957f18\u4f4d\uff0c__int 128 128\u4f4d\u3002\u6240\u4ee5\u8ba1\u7b97pow(k, i)\u4e0d\u80fd\u76f4\u63a5\u7b97\uff0c\u4f1a\u6ea2\u51fa\uff0c\u6240\u4ee5\u8fb9\u4e58\u8fb9\u7b97\u3002<\/p>\n

\u4ee3\u7801<\/h2>\n
#include <algorithm>\n#include <bitset>\n#include <cmath>\n#include <cstdio>\n#include <cstdlib>\n#include <cstring>\n#include <fstream>\n#include <iostream>\n#include <map>\n#include <queue>\n#include <set>\n#include <stack>\n#include <unordered_map>\n#include <unordered_set>\n#include <vector>\n\n#define x first\n#define y second\n#define endl '\\n'\n#define IOS                       \\\n    ios_base::sync_with_stdio(0); \\\n    cin.tie(0);                   \\\n    cout.tie(0);\n\nusing namespace std;\n\ntypedef long long ll;\ntypedef pair<ll, ll> pll;\ntypedef pair<int, int> pii;\ntypedef unsigned long long ull;\n\nconst int INF = 0x3f3f3f3f, mod = 1000000007;\nconst int N = 2e5 + 10;\nconst ll P = 1e9, K = 2e18;\nll check(ll k, ll cnt)\n{\n    __int128 s = 1, pr = 1;\n    for (ll i = 1; i <= cnt; i++) {\n        pr = pr * k;\n        s += pr;\n        if (s >= K)\n            return K;\n    }\n    ll res = s;\n    return res;\n}\nvoid solve()\n{\n    ll n;\n    cin >> n;\n    for (ll i = 2; i <= 62; i++) {\n        ll l = 2, r = P;\n        while (l < r) {\n            ll mid = (l + r) \/ 2;\n            ll x = check(mid, i);\n            if (x == n) {\n                cout << "YES\\n";\n                return;\n            } else if (x > n)\n                r = mid;\n            else\n                l = mid + 1;\n        }\n    }\n    cout << "NO\\n";\n}\nint main()\n{\n    IOS;\n    int _ = 1;\n    cin >> _;\n    while (_--) {\n        solve();\n    }\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee\u94fe\u63a5 \u94fe\u63a5 \u9898\u76ee\u5927\u610f \u95ee\u6709\u6ca1\u6709\u751f\u6210\u7684\u96ea\u82b1\u8282\u70b9\u6570\u7b49\u4e8en?\u96ea\u82b1\u662f\u521a\u5f00\u59cb\u662f\u4e00\u4e2a\u70b9\uff0c\u540e\u9762\u4ece\u4e00\u4e2a\u70b9\u8fde\u63a5K\u4e2a\u8282\u70b9\uff0c\u518d\u4ecek\u4e2a\u8282\u70b9\u518d\u8fde\u63a5K\u4e2a\u70b9\uff0ceasy\u7248\u672c\u662fn<=1e6,hard version\u662fn<=1e18 \u9898\u89e3 easy\u7248\u672c\u66b4\u529b\u5373\u53ef\uff0c\u76f4\u63a5\u9884\u5904\u7406\u51fa\u6240\u6709\u7684\u60c5\u51b5\uff0c\u521a\u5f00\u59cb\u96ea\u82b1\u8282\u70b9\u6570\u76ee\u662f\uff0c1 + k + k ^2\uff0c\u7136\u540e\u6bcf\u6b21\u52a0K^i\uff0chard version\u4e0d\u80fd\u8fd9\u6837\u5199\uff0c\u56e0\u4e3a\u65f6\u95f4\u590d\u6742\u5ea6\u592a\u9ad8\u4e86\uff0c\u6240\u4ee5\u6211\u4eec\u4f7f\u7528\u4e8c\u5206\u641c\u7d22\uff0cint\u662f2^32\uff0c\u7ea6\u4e3a10\u4f4d\uff0clong long 64\u4f4d\uff0c\u7ea6\u957f18\u4f4d\uff0c__int 128 128\u4f4d\u3002\u6240\u4ee5\u8ba1\u7b97pow(k, i)\u4e0d\u80fd\u76f4\u63a5\u7b97\uff0c\u4f1a\u6ea2\u51fa\uff0c\u6240\u4ee5\u8fb9\u4e58\u8fb9\u7b97\u3002 \u4ee3\u7801 #include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <fstream> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <unordered_map> #include <unordered_set> #include <vector> #define x first #define y second […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[39,11,46],"class_list":["post-250","post","type-post","status-publish","format-standard","hentry","category-solution","tag-39","tag-11","tag-46"],"_links":{"self":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/250","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=250"}],"version-history":[{"count":0,"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/250\/revisions"}],"wp:attachment":[{"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=250"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=250"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=250"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}