{"id":284,"date":"2019-09-25T14:41:17","date_gmt":"2019-09-25T06:41:17","guid":{"rendered":"http:\/\/www.guanhaobo.cn\/?p=284"},"modified":"2019-09-25T14:41:17","modified_gmt":"2019-09-25T06:41:17","slug":"%e6%b4%9b%e8%b0%b7-p1218-usaco1-5%e7%89%b9%e6%ae%8a%e7%9a%84%e8%b4%a8%e6%95%b0%e8%82%8b%e9%aa%a8-superprime-rib","status":"publish","type":"post","link":"https:\/\/www.guanhaobo.cn\/?p=284","title":{"rendered":"\u6d1b\u8c37 P1218 \u2014 [USACO1.5]\u7279\u6b8a\u7684\u8d28\u6570\u808b\u9aa8 Superprime Rib"},"content":{"rendered":"

\u9898\u76ee\u63cf\u8ff0<\/h3>\n

\u519c\u6c11\u7ea6\u7ff0\u7684\u6bcd\u725b\u603b\u662f\u4ea7\u751f\u6700\u597d\u7684\u808b\u9aa8\u3002\u4f60\u80fd\u901a\u8fc7\u519c\u6c11\u7ea6\u7ff0\u548c\u7f8e\u56fd\u519c\u4e1a\u90e8\u6807\u8bb0\u5728\u6bcf\u6839\u808b\u9aa8\u4e0a\u7684\u6570\u5b57\u8ba4\u51fa\u5b83\u4eec\u3002\u519c\u6c11\u7ea6\u7ff0\u786e\u5b9a\u4ed6\u5356\u7ed9\u4e70\u65b9\u7684\u662f\u771f\u6b63\u7684\u8d28\u6570\u808b\u9aa8,\u662f\u56e0\u4e3a\u4ece\u53f3\u8fb9\u5f00\u59cb\u5207\u4e0b\u808b\u9aa8,\u6bcf\u6b21\u8fd8\u5269\u4e0b\u7684\u808b\u9aa8\u4e0a\u7684\u6570\u5b57\u90fd\u7ec4\u6210\u4e00\u4e2a\u8d28\u6570,\u4e3e\u4f8b\u6765\u8bf4: 7 3 3 1 \u5168\u90e8\u808b\u9aa8\u4e0a\u7684\u6570\u5b57 7331\u662f\u8d28\u6570;\u4e09\u6839\u808b\u9aa8 733\u662f\u8d28\u6570;\u4e8c\u6839\u808b\u9aa8 73 \u662f\u8d28\u6570;\u5f53\u7136,\u6700\u540e\u4e00\u6839\u808b\u9aa8 7 \u4e5f\u662f\u8d28\u6570\u3002 7331 \u88ab\u53eb\u505a\u957f\u5ea6 4 \u7684\u7279\u6b8a\u8d28\u6570\u3002\u5199\u4e00\u4e2a\u7a0b\u5e8f\u5bf9\u7ed9\u5b9a\u7684\u808b\u9aa8\u7684\u6570\u76ee N (1<=N<=8),\u6c42\u51fa\u6240\u6709\u7684\u7279\u6b8a\u8d28\u6570\u3002\u6570\u5b571\u4e0d\u88ab\u770b\u4f5c\u4e00\u4e2a\u8d28\u6570\u3002<\/p>\n

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

https:\/\/www.luogu.org\/problem\/P1218<\/a><\/p>\n

\u8f93\u5165\u683c\u5f0f<\/h3>\n

\u5355\u72ec\u7684\u4e00\u884c\u5305\u542bN\u3002<\/p>\n

\u8f93\u51fa\u683c\u5f0f<\/h3>\n

\u6309\u987a\u5e8f\u8f93\u51fa\u957f\u5ea6\u4e3a N \u7684\u7279\u6b8a\u8d28\u6570,\u6bcf\u884c\u4e00\u4e2a\u3002<\/p>\n

\u8f93\u5165\u6837\u4f8b<\/h3>\n

4<\/code><\/p>\n

\u8f93\u51fa\u6837\u4f8b<\/h3>\n
2333\n2339\n2393\n2399\n2939\n3119\n3137\n3733\n3739\n3793\n3797\n5939\n7193\n7331\n7333\n7393\n<\/code><\/pre>\n
\u8bf4\u660e\/\u63d0\u793a<\/h3>\n
\u9898\u76ee\u7ffb\u8bd1\u6765\u81eaNOCOW\u3002
\nUSACO Training Section 1.5<\/p>\n
\u9898\u76ee\u5206\u6790<\/h3>\n
N \u7684\u8303\u56f4\u662f1\u52308\uff0c\u6240\u4ee5\u53ef\u4ee5\u76f4\u63a5\u6253\u8868\uff0c\u6253\u8868\u5c31\u662f\u8bf4\u5148\u628a\u7b54\u6848\u8ba1\u7b97\u51fa\u6765\uff0c\u7136\u540e\u5199\u5728\u4ee3\u7801\u91cc\u3002
\n\u5982\u679c\u4e0d\u6253\u8868\u600e\u4e48\u5199\u5462\uff1f
\n\u76f4\u63a5\u679a\u4e3e\u80af\u5b9a\u662f\u4f1a\u8d85\u65f6\u7684\u3002
\n\u5bf9\u4e8e\u4e00\u4e2aN\u4f4d\u7684\u7279\u6b8a\u8d28\u6570\uff0c\u5b83\u7684\u524d N-1 \u4f4d\u4e00\u5b9a\u4e5f\u662f\u7279\u6b8a\u8d28\u6570\uff0c\u6240\u4ee5\u6211\u4eec\u5728\u6c42N\u4f4d\u7684\u7279\u6b8a\u8d28\u6570\u65f6\uff0c\u53ea\u8981\u5148\u6c42\u51fa N-1 \u4f4d\u7684\u7279\u6b8a\u8d28\u6570\uff0c\u7136\u540e\u5728\u6b64\u57fa\u7840\u4e0a\u8fdb\u884c\u679a\u4e3e\u5373\u53ef\u3002
\n\u6240\u4ee5\uff0c\u75311\u4f4d\u7279\u6b8a\u8d28\u6570\u53ef\u4ee5\u6c42\u51fa2\u4f4d\u7279\u6b8a\u8d28\u6570\uff0c\u75312\u4f4d\u7279\u6b8a\u8d28\u6570\u6c42\u51fa3\u4f4d\u7279\u6b8a\u8d28\u6570\uff0c\u4ee5\u6b64\u7c7b\u63a8\u3002
\n\u6df1\u5ea6\u4f18\u5148\u641c\u7d22\u3002<\/p>\n
AC\u4ee3\u7801<\/h3>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint MAX;\n\nint zhishu(int n)\n{\n    int i;\n    if (n == 2)\n        return 1;\n    if (n % 2 == 0 || n < 2)\n        return 0;\n    for (i = 3; i <= sqrt(n); i += 2)\n    {\n        if (n % i == 0)\n            break;\n    }\n    if (i > sqrt(n))\n        return 1;\n    return 0;\n}\n\nvoid dfs(int num, int n)\n{\n    for (int i = 1; i <= 9; i++)\n    {\n        if (zhishu(num * 10 + i))\n        {\n            if (n == MAX)\n                printf(\"%d\\n\", num * 10 + i);\n            else\n                dfs(num * 10 + i, n + 1);\n        }\n    }\n}\n\nint main()\n{\n    cin >> MAX;\n    dfs(0, 1);\n    return 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee\u63cf\u8ff0 \u519c\u6c11\u7ea6\u7ff0\u7684\u6bcd\u725b\u603b\u662f\u4ea7\u751f\u6700\u597d\u7684\u808b\u9aa8\u3002\u4f60\u80fd\u901a\u8fc7\u519c\u6c11\u7ea6\u7ff0\u548c\u7f8e\u56fd\u519c\u4e1a\u90e8\u6807\u8bb0\u5728\u6bcf\u6839\u808b\u9aa8\u4e0a\u7684\u6570\u5b57\u8ba4\u51fa\u5b83\u4eec\u3002\u519c\u6c11\u7ea6 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[11,56],"class_list":["post-284","post","type-post","status-publish","format-standard","hentry","category-algo","tag-dfs","tag-56"],"_links":{"self":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/284","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=284"}],"version-history":[{"count":0,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/284\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=284"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=284"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=284"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}