{"id":168,"date":"2025-08-13T06:09:17","date_gmt":"2025-08-13T06:09:17","guid":{"rendered":"https:\/\/www.starluo.top\/?p=168"},"modified":"2025-08-13T06:09:18","modified_gmt":"2025-08-13T06:09:18","slug":"noip-2001-%e6%99%ae%e5%8f%8a%e7%bb%84-%e6%9c%80%e5%a4%a7%e5%85%ac%e7%ba%a6%e6%95%b0%e5%92%8c%e6%9c%80%e5%b0%8f%e5%85%ac%e5%80%8d%e6%95%b0%e9%97%ae%e9%a2%98","status":"publish","type":"post","link":"https:\/\/www.starluo.top\/?p=168","title":{"rendered":"[NOIP 2001 \u666e\u53ca\u7ec4] \u6700\u5927\u516c\u7ea6\u6570\u548c\u6700\u5c0f\u516c\u500d\u6570\u95ee\u9898"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">\u9898\u9762<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">\u9898\u76ee\u63cf\u8ff0<\/h3>\n\n\n\n<p>\u8f93\u5165\u4e24\u4e2a\u6b63\u6574\u6570 $x_0, y_0$\uff0c\u6c42\u51fa\u6ee1\u8db3\u4e0b\u5217\u6761\u4ef6\u7684 $P, Q$ \u7684\u4e2a\u6570\uff1a<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>$P,Q$ \u662f\u6b63\u6574\u6570\u3002<\/li>\n\n\n\n<li>\u8981\u6c42 $P, Q$ \u4ee5 $x_0$ \u4e3a\u6700\u5927\u516c\u7ea6\u6570\uff0c\u4ee5 $y_0$ \u4e3a\u6700\u5c0f\u516c\u500d\u6570\u3002<\/li>\n<\/ol>\n\n\n\n<p>\u8bd5\u6c42\uff1a\u6ee1\u8db3\u6761\u4ef6\u7684\u6240\u6709\u53ef\u80fd\u7684 $P, Q$ \u7684\u4e2a\u6570\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u8f93\u5165\u683c\u5f0f<\/h3>\n\n\n\n<p>\u4e00\u884c\u4e24\u4e2a\u6b63\u6574\u6570 $x_0, y_0$\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u8f93\u51fa\u683c\u5f0f<\/h3>\n\n\n\n<p>\u4e00\u884c\u4e00\u4e2a\u6570\uff0c\u8868\u793a\u6c42\u51fa\u6ee1\u8db3\u6761\u4ef6\u7684 $P, Q$ \u7684\u4e2a\u6570\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u8f93\u5165\u8f93\u51fa\u6837\u4f8b #1<\/h3>\n\n\n\n<h4 class=\"wp-block-heading\">\u8f93\u5165 #1<\/h4>\n\n\n\n<pre class=\"wp-block-code\"><code>3 60<\/code><\/pre>\n\n\n\n<h4 class=\"wp-block-heading\">\u8f93\u51fa #1<\/h4>\n\n\n\n<pre class=\"wp-block-code\"><code>4<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">\u8bf4\u660e\/\u63d0\u793a<\/h3>\n\n\n\n<p>$P,Q$ \u6709 $4$ \u79cd\uff1a<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>$3, 60$\u3002<\/li>\n\n\n\n<li>$15, 12$\u3002<\/li>\n\n\n\n<li>$12, 15$\u3002<\/li>\n\n\n\n<li>$60, 3$\u3002<\/li>\n<\/ol>\n\n\n\n<p>\u5bf9\u4e8e $100\\%$ \u7684\u6570\u636e\uff0c$2 \\le x_0, y_0 \\le {10}^5$\u3002<\/p>\n\n\n\n<p><strong>\u3010\u9898\u76ee\u6765\u6e90\u3011<\/strong><\/p>\n\n\n\n<p>NOIP 2001 \u666e\u53ca\u7ec4\u7b2c\u4e8c\u9898<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u9898\u89e3<\/h2>\n\n\n\n<p>\u4e00\u9053\u6570\u8bba\u9898\u3002<\/p>\n\n\n\n<p>\u9996\u5148\u5224\u65ad$x_0$\u662f\u5426\u4e3a$y_0$\u7684\u7ea6\u6570\u3002\u5982\u679c\u4e0d\u662f\uff0c\u7531\u6700\u5c0f\u516c\u500d\u6570\u7684\u7ea6\u6570\u5fc5\u5b9a\u5305\u542b\u6700\u5927\u516c\u7ea6\u6570\u53ef\u77e5\uff0c\u6570\u5bf9$P, Q$\u4e0d\u53ef\u80fd\u5b58\u5728\uff0c\u5219\u8f93\u51fa$0$\u3002<\/p>\n\n\n\n<p>\u5176\u6b21\uff0c\u6211\u4eec\u8003\u8651\u6570\u5bf9$P, Q$\u7684\u751f\u6210\u65b9\u5f0f\u3002\u5bf9$x_0, y_0$\u8fdb\u884c\u8d28\u56e0\u6570\u5206\u89e3\uff0c\u8bbe\u4e3a\uff1a<\/p>\n\n\n\n<p>$x_0={p_1}^{m_1}*{p_2}^{m_2}*\\cdots*{p_j}^{m_j}$<\/p>\n\n\n\n<p>$y_0={p_1}^{m_1}*{p_2}^{m_2}*\\cdots*{p_j}^{m_j}*{q_1}^{n_1}*{q_2}^{n_2}*\\cdots*{q_k}^{n_k}$<\/p>\n\n\n\n<p>\u5176\u4e2d$q_1, q_2, \\cdots, q_k$\u53ef\u80fd\u4e0e$p_1, p_2, \\cdots, p_j$\u7684\u90e8\u5206\u6216\u5168\u90e8\u91cd\u5408\u3002<\/p>\n\n\n\n<p>\u7531\u9898\u610f\uff0c\u5f97\u5230$P, Q$\u751f\u6210\u7684\u5982\u4e0b\u7ea6\u675f\u6761\u4ef6\uff1a<\/p>\n\n\n\n<p>\u2460\u6700\u5927\u516c\u7ea6\u6570\u662f$x_0$\uff0c\u5219$P, Q$\u7684\u516c\u7ea6\u6570\u4e0d\u80fd\u51fa\u73b0\u9664{p_1}^{m_1}, {p_2}^{m_2}, \\cdots*, {p_j}^{m_j}\u53ca\u5b83\u4eec\u7684\u4f4e\u6b21\u5e42\u4ee5\u5916\u7684\u7ea6\u6570\u3002<\/p>\n\n\n\n<p>\u53cd\u4f8b\uff1a$x_0=3, y_0=60$\uff0c\u6784\u9020\u4e86$P=6, Q=30$\uff08\u5c06$y_0$\u7684\u4e00\u4e2a\u7ea6\u6570$2$\u8f6c\u79fb\u7ed9$x_0$\uff09\uff0c\u6b64\u65f6$P, Q$\u7684\u6700\u5927\u516c\u7ea6\u6570\u662f$6$\u800c\u975e$3$\u3002<\/p>\n\n\n\n<p>\u2461\u6700\u5c0f\u516c\u500d\u6570\u662f$y_0$\uff0c\u5219$P, Q$\u4e2d\u5747\u4e0d\u53ef\u80fd\u51fa\u73b0\u9664$p_i, q_i$\u4ee5\u5916\u7684\u7ea6\u6570\u3002<\/p>\n\n\n\n<p>\u7efc\u4e0a\uff0c\u6211\u4eec\u53ef\u4ee5\u5f97\u51fa\u6570\u5bf9$P, Q$\u7684\u751f\u6210\u65b9\u5f0f\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u524d\u63d0\uff1a$(x_0, y_0)$\u662f\u4e00\u7ec4\u5408\u6cd5\u7684$(P, Q)$\u3002\u5426\u5219$(P, Q)$\u4e0d\u5b58\u5728\u3002<\/li>\n\n\n\n<li>\u5bf9$\\frac{y_0}{x_0}$\u7684\u7ed3\u679c\u8fdb\u884c\u8d28\u56e0\u6570\u5206\u89e3\uff0c\u5f97\u5230<\/li>\n<\/ul>\n\n\n\n<p class=\"has-text-align-center\">$\\frac{y_0}{x_0}={q_1}^{n_1}*{q_2}^{n_2}*\\cdots*{q_k}^{n_k}$<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u5c06\u4e0a\u5f0f\u4e2d\u7684${q_i}^{n_i}$\u89c6\u4e3a<strong>\u4e00\u7ec4\u8d28\u56e0\u6570<\/strong>\uff0c\u5c06<strong>\u5b8c\u6574\u7684\u4e00\u7ec4\u6216\u591a\u7ec4\u8d28\u56e0\u6570<\/strong>\u7531$y_0$\u8f6c\u79fb\u81f3$x_0$\u3002<\/li>\n\n\n\n<li>\u56e0\u6b64\uff0c\u7b54\u6848\u4e3a$2^k$\u3002\uff08\u5206\u6b65\u4e58\u6cd5\u539f\u7406\uff1a\u6bcf\u4e00\u7ec4\u8d28\u56e0\u6570\u90fd\u6709\u201c\u8f6c\u79fb\u201d\u6216\u201c\u4e0d\u8f6c\u79fb\u201d\u4e24\u79cd\u72b6\u6001\u3002\uff09<\/li>\n<\/ul>\n\n\n\n<p>\u5b8c\u6574\u4ee3\u7801\u5982\u4e0b\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;cstdio>\n#include&lt;cmath>\nint x,y,cnt=0,s&#91;100001],f=2;\nbool p(int x)\n{\n\tif(s&#91;x]||x==2) return false;\n\tfor(int i=2;i&lt;=sqrt(x)+1;i++)\n\t{\n\t\tif(!(x%i)) return true;\n\t}\n\ts&#91;x]=1; \/\/\u8d28\u6570\u5224\u65ad\u7ed3\u679c\u8bb0\u5fc6\u5316\n\treturn false;\n}\nint main()\n{\n\tscanf(\"%d%d\",&amp;x,&amp;y);\n\tif(y%x)\n\t{\n\t\tprintf(\"0\");\n\t\treturn 0;\n\t}\n\ty\/=x;\n\twhile(y>1)\n\t{\n\t\tfor(int i=f;i&lt;=y;i++)\n\t\t{\n\t\t\tif(y%i||p(i)) continue;\n\t\t\twhile(!(y%i)) y\/=i;\n\t\t\tf=i; \/\/\u8d28\u56e0\u6570\u5206\u89e3\u7ed3\u679c\u8bb0\u5fc6\u5316\n\t\t\tcnt++;\n\t\t\tbreak;\n\t\t}\n\t}\n\tprintf(\"%d\",1&lt;&lt;cnt); \/\/\u7b49\u4ef7\u4e8epow(2,cnt);\n\treturn 0;\n} <\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u9762 \u9898\u76ee\u63cf\u8ff0 \u8f93\u5165\u4e24\u4e2a\u6b63\u6574\u6570 $x_0, y_0$\uff0c\u6c42\u51fa\u6ee1\u8db3\u4e0b\u5217\u6761\u4ef6\u7684 $P, Q$ \u7684\u4e2a\u6570\uff1a \u8bd5\u6c42\uff1a\u6ee1\u8db3\u6761\u4ef6\u7684\u6240\u6709\u53ef\u80fd\u7684 $P &#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"emotion":"","emotion_color":"","title_style":"","license":"","footnotes":""},"categories":[8,1],"tags":[],"class_list":["post-168","post","type-post","status-publish","format-standard","hentry","category-oi","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.starluo.top\/index.php?rest_route=\/wp\/v2\/posts\/168","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.starluo.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.starluo.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.starluo.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.starluo.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=168"}],"version-history":[{"count":5,"href":"https:\/\/www.starluo.top\/index.php?rest_route=\/wp\/v2\/posts\/168\/revisions"}],"predecessor-version":[{"id":173,"href":"https:\/\/www.starluo.top\/index.php?rest_route=\/wp\/v2\/posts\/168\/revisions\/173"}],"wp:attachment":[{"href":"https:\/\/www.starluo.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=168"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.starluo.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=168"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.starluo.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=168"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}