{"id":279,"date":"2018-05-29T11:52:39","date_gmt":"2018-05-29T11:52:39","guid":{"rendered":"https:\/\/www.haoyuan.info\/?p=279"},"modified":"2018-06-12T01:31:54","modified_gmt":"2018-06-12T01:31:54","slug":"2018-%e8%ae%a1%e8%92%9c%e4%b9%8b%e9%81%93-%e7%ac%ac%e4%ba%94%e5%9c%ba","status":"publish","type":"post","link":"https:\/\/haoyuan.info\/?p=279","title":{"rendered":"2018 \u8ba1\u849c\u4e4b\u9053 \u521d\u8d5b \u7b2c\u4e94\u573a"},"content":{"rendered":"

\u7531\u9898\u53ef\u77e5\u6700\u5927\u60c5\u51b5\u4e3a(n + 1) * 3 * 3 – n\uff0c\u7136\u800c\u6211\u4eec\u65e0\u6cd5\u5f97\u77e5\u6700\u5c0f\u60c5\u51b5\u65f6\u4e09\u4e2a\u6570\u4e4b\u95f4\u7684\u5173\u7cfb\u3002<\/p>\n

\u6545\u8003\u8651DP\u6253\u8868\uff0c\u7b97\u51fa\u67d0\u4e2a\u6570\u4e24\u4e2a\u6570\u76f8\u4e58\u65f6\u6700\u5c0f\u7684\u503c\uff0c\u7531\u8be5\u503c\u9012\u63a8\u7b2c\u4e09\u4e2a\u6570\u3002<\/p>\n

\u6253\u8868\u7b97\u6cd5O(nlogn)\uff0c\u67e5\u8be2O(1)<\/p>\n

A\u9898\u4ee3\u7801<\/h2>\n
#pragma GCC optimize(\"O3\")\n#include <iostream>\n#include <vector>\n#include <array>\n#include <queue>\n#include <algorithm>\n#include <deque>\n#include <cmath>\n#include <cstring>\n\nusing namespace std;\nusing ll = long long;\nusing pii = pair<int, int>;\nconst int maxn = 1e6 + 6;\nint T, n;\narray<int, maxn> dp, dp2;\n\nint main() {\n    ios::sync_with_stdio(false);\n    ([&]() -> void {\n        dp.fill(1e9);\n        dp2.fill(1e9);\n        for (int i = 1; i <= 1e6; ++i) {\n            for (int j = 1; i * j <= 1e6; ++j) {\n                dp[i * j] = min(dp[i * j], (i + 2) * (j + 2));\n            }\n        }\n        for (int i = 1; i <= 1e6; ++i) {\n            for (int j = 1; i * j <= 1e6; ++j) {\n                dp2[i * j] = min(dp2[i * j], dp[i] * (j + 1));\n            }\n        }\n    })();\n    cin >> T;\n    while (T--) {\n        cin >> n;\n        int ansmax = (n + 1) * 3 * 3 - n;\n        int ansmin = dp2[n] - n;\n        cout << ansmin << \" \" << ansmax << endl;\n    }\n}\n<\/code><\/pre>\n
B<\/h2>\n
\u6839\u636e\u9898\u610f\u679a\u4e3en\u8303\u56f4\u5185\u7684f(x),\u7528\u54c8\u5e0c\u8868\u4fdd\u5b58\uff0c\u6253\u8868\u7ed3\u675f\u540e\u5bf9\u8868\u8fdb\u884c\u679a\u4e3e\uff0c\u7b97\u51fa\u7b26\u5408\u6761\u4ef6\u7684\u4e2a\u6570\u5373\u53ef<\/p>\n
B\/C\u9898\u4ee3\u7801:<\/h4>\n
\n#pragma GCC optimize(\"O3\")\n\n#include <iostream>\n#include <algorithm>\n#include <array>\n#include <limits>\n#include <cmath>\n#include <map>\n#include <iomanip>\n#include <unordered_map>\n#include <regex>\n#include <queue>\n#include <functional>\n\nusing namespace std;\nusing ll = long long;\nusing db = double;\nusing pll = pair<ll, ll>;\nconst ll mod = 998244353;\n\nll f(ll x) {\n    ll ans = 1;\n    while (x) {\n        ans *= (x % 10);\n        x \/= 10;\n    }\n    return ans;\n}\n\nunordered_map<ll, ll> mp;\n\nint main() {\n    ios::sync_with_stdio(false);\n    ll n, k;\n    cin >> n >> k;\n    ll cnt = 0;\n    for (ll i = 1; i <= n; ++i) {\n        ll fi = f(i);\n        if (fi)\n            ++mp[fi];\n    }\n    for (auto i:mp) {\n        for (auto j:mp) {\n            ll g = __gcd(i.first, j.first);\n            if (g > 0 && g <= k) {\n                cnt = (cnt + i.second * j.second) % mod;\n            }\n        }\n    }\n    cout << cnt << endl;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u7531\u9898\u53ef\u77e5\u6700\u5927\u60c5\u51b5\u4e3a(n + 1) * 3 * 3 – n\uff0c\u7136\u800c\u6211\u4eec\u65e0\u6cd5\u5f97\u77e5\u6700\u5c0f\u60c5\u51b5\u65f6\u4e09\u4e2a\u6570\u4e4b\u95f4\u7684\u5173 […]<\/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":[22],"tags":[24,27,36],"class_list":["post-279","post","type-post","status-publish","format-standard","hentry","category-22","tag-cpp","tag-dp","tag-36"],"jetpack_featured_media_url":"","jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p8UC2c-4v","jetpack_likes_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/279","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=279"}],"version-history":[{"count":9,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/279\/revisions"}],"predecessor-version":[{"id":306,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/279\/revisions\/306"}],"wp:attachment":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=279"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=279"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=279"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}