{"id":1520,"date":"2026-05-16T09:18:26","date_gmt":"2026-05-16T01:18:26","guid":{"rendered":"http:\/\/wordpress.fangt.online\/?p=1520"},"modified":"2026-05-16T09:18:26","modified_gmt":"2026-05-16T01:18:26","slug":"%e5%88%9d%e7%ad%89%e6%95%b0%e8%ae%ba%e6%a6%82%e5%bf%b5%e6%a2%b3%e7%90%86","status":"publish","type":"post","link":"http:\/\/wordpress.fangt.online\/index.php\/2026\/05\/16\/%e5%88%9d%e7%ad%89%e6%95%b0%e8%ae%ba%e6%a6%82%e5%bf%b5%e6%a2%b3%e7%90%86\/","title":{"rendered":"\u521d\u7b49\u6570\u8bba\u6982\u5ff5\u68b3\u7406"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">\u4e00\u3001\u6982\u5ff5\u4e0e\u6027\u8d28\u68b3\u7406<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">1. \u7d20\u6570\u4e0e\u5408\u6570<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>\u7d20\u6570<\/strong>\uff1a\u5927\u4e8e 1\uff0c\u53ea\u6709 1 \u548c\u81ea\u8eab\u4e24\u4e2a\u6b63\u56e0\u6570<\/li>\n\n\n\n<li><strong>\u5408\u6570<\/strong>\uff1a\u5927\u4e8e 1\uff0c\u6709\u9664 1 \u548c\u81ea\u8eab\u5916\u7684\u5176\u4ed6\u56e0\u6570<\/li>\n\n\n\n<li><strong>1 \u548c 0<\/strong>\uff1a\u65e2\u975e\u7d20\u6570\u4e5f\u975e\u5408\u6570<\/li>\n\n\n\n<li>\u5224\u5b9a\uff1a\u8bd5\u9664\u6cd5 ( <math data-latex=\"O(\\sqrt{n}) \"><semantics><mrow><mi>O<\/mi><mo form=\"prefix\" stretchy=\"false\">(<\/mo><msqrt><mi>n<\/mi><\/msqrt><mo form=\"postfix\" stretchy=\"false\">)<\/mo><\/mrow><annotation encoding=\"application\/x-tex\">O(\\sqrt{n}) <\/annotation><\/semantics><\/math>)<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">2. \u6700\u5927\u516c\u7ea6\u6570\uff08GCD\uff09<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u82e5\u5e72\u6570\u516c\u5171\u56e0\u6570\u4e2d\u7684\u6700\u5927\u503c<\/li>\n\n\n\n<li>\u6027\u8d28\uff1a( <math data-latex=\"\\gcd(a, b) = \\gcd(b, a\\bmod b) \"><semantics><mrow><mrow><mi>gcd<\/mi><mo>\u2061<\/mo><\/mrow><mo form=\"prefix\" stretchy=\"false\">(<\/mo><mi>a<\/mi><mo separator=\"true\">,<\/mo><mi>b<\/mi><mo form=\"postfix\" stretchy=\"false\">)<\/mo><mo>=<\/mo><mrow><mi>gcd<\/mi><mo>\u2061<\/mo><\/mrow><mo form=\"prefix\" stretchy=\"false\">(<\/mo><mi>b<\/mi><mo separator=\"true\">,<\/mo><mi>a<\/mi><mo lspace=\"0.2222em\" rspace=\"0.2222em\">mod<\/mo><mi>b<\/mi><mo form=\"postfix\" stretchy=\"false\">)<\/mo><\/mrow><annotation encoding=\"application\/x-tex\">\\gcd(a, b) = \\gcd(b, a\\bmod b) <\/annotation><\/semantics><\/math>)<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">3. \u6700\u5c0f\u516c\u500d\u6570\uff08LCM\uff09<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>( <math data-latex=\"\\mathrm{lcm}(a, b) = \\frac{a \\times b}{\\gcd(a, b)}\"><semantics><mrow><mrow><mtext><\/mtext><mi>lcm<\/mi><\/mrow><mo form=\"prefix\" stretchy=\"false\">(<\/mo><mi>a<\/mi><mo separator=\"true\">,<\/mo><mi>b<\/mi><mo form=\"postfix\" stretchy=\"false\">)<\/mo><mo>=<\/mo><mfrac><mrow><mi>a<\/mi><mo>\u00d7<\/mo><mi>b<\/mi><\/mrow><mrow><mrow><mi>gcd<\/mi><mo>\u2061<\/mo><\/mrow><mo form=\"prefix\" stretchy=\"false\">(<\/mo><mi>a<\/mi><mo separator=\"true\">,<\/mo><mi>b<\/mi><mo form=\"postfix\" stretchy=\"false\" lspace=\"0em\" rspace=\"0em\">)<\/mo><\/mrow><\/mfrac><\/mrow><annotation encoding=\"application\/x-tex\">\\mathrm{lcm}(a, b) = \\frac{a \\times b}{\\gcd(a, b)}<\/annotation><\/semantics><\/math> )<\/li>\n\n\n\n<li>\u6ce8\u610f\uff1a\u9632\u6b62\u6ea2\u51fa\uff08\u5148\u9664\u540e\u4e58\uff09<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">4. \u540c\u4f59\u4e0e\u6a21\u8fd0\u7b97<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>( <math data-latex=\"a \\equiv b \\pmod{m}\"><semantics><mrow><mi>a<\/mi><mo>\u2261<\/mo><mi>b<\/mi><mo><\/mo><mspace width=\"0.4444em\"><\/mspace><mo form=\"prefix\" stretchy=\"false\">(<\/mo><mrow><mtext><\/mtext><mi>mod<\/mi><\/mrow><mspace width=\"0.3333em\"><\/mspace><mi>m<\/mi><mo form=\"postfix\" stretchy=\"false\">)<\/mo><\/mrow><annotation encoding=\"application\/x-tex\">a \\equiv b \\pmod{m}<\/annotation><\/semantics><\/math> ) \u8868\u793a (<math data-latex=\" m \\mid a-b\"><semantics><mrow><mi>m<\/mi><mo lspace=\"0.22em\" rspace=\"0.22em\" stretchy=\"false\">|<\/mo><mi>a<\/mi><mo>\u2212<\/mo><mi>b<\/mi><\/mrow><annotation encoding=\"application\/x-tex\"> m \\mid a-b<\/annotation><\/semantics><\/math> )<\/li>\n\n\n\n<li>\u8fd0\u7b97\u6027\u8d28\uff1a<\/li>\n\n\n\n<li>\u52a0\u6cd5\/\u4e58\u6cd5\u53ef\u5206\u522b\u53d6\u6a21<\/li>\n\n\n\n<li>\u6ca1\u6709\u9664\u6cd5\uff08\u9700\u7528\u9006\u5143\uff0c\u4f46\u4e94\u7ea7\u4e00\u822c\u4ec5\u8003\u540c\u4f59\u57fa\u672c\u6982\u5ff5\uff09<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">5. \u7ea6\u6570\u4e0e\u500d\u6570<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>( <math data-latex=\"d \\mid n\"><semantics><mrow><mi>d<\/mi><mo lspace=\"0.22em\" rspace=\"0.22em\" stretchy=\"false\">|<\/mo><mi>n<\/mi><\/mrow><annotation encoding=\"application\/x-tex\">d \\mid n<\/annotation><\/semantics><\/math> )\uff1a( d ) \u662f ( n ) \u7684\u7ea6\u6570<\/li>\n\n\n\n<li>\u901a\u8fc7\u8d28\u56e0\u6570\u5206\u89e3\u6c42\u7ea6\u6570\u4e2a\u6570\u3001\u7ea6\u6570\u548c<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">6. \u8d28\u56e0\u6570\u5206\u89e3<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u552f\u4e00\u5206\u89e3\u5b9a\u7406\uff1a( <math data-latex=\"n = p_1^{k_1} p_2^{k_2} \\dots\"><semantics><mrow><mi>n<\/mi><mo>=<\/mo><msubsup><mi>p<\/mi><mn>1<\/mn><msub><mi>k<\/mi><mn>1<\/mn><\/msub><\/msubsup><msubsup><mi>p<\/mi><mn>2<\/mn><msub><mi>k<\/mi><mn>2<\/mn><\/msub><\/msubsup><mo>\u2026<\/mo><\/mrow><annotation encoding=\"application\/x-tex\">n = p_1^{k_1} p_2^{k_2} \\dots<\/annotation><\/semantics><\/math> )<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">7. \u5947\u5076\u6027<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u52a0\u51cf\uff1a\u5947+\u5947=\u5076\uff1b\u5947+\u5076=\u5947\uff1b\u5947-\u5947=\u5076<\/li>\n\n\n\n<li>\u4e58\uff1a\u6709\u5076\u5219\u5076\uff1b\u5168\u5947\u4e3a\u5947<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">\u4e8c\u3001\u6838\u5fc3\u7b97\u6cd5<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">1. \u8f97\u8f6c\u76f8\u9664\u6cd5\uff08\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\uff09<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>gcd(a, b):\n    while b != 0:\n        a, b = b, a % b\n    return a<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u590d\u6742\u5ea6<\/strong>\uff1a( <math data-latex=\"O(\\log \\min(a,b))\"><semantics><mrow><mi>O<\/mi><mo form=\"prefix\" stretchy=\"false\">(<\/mo><mrow><mi>log<\/mi><mo>\u2061<\/mo><mspace width=\"0.1667em\"><\/mspace><\/mrow><mrow><mi>min<\/mi><mo>\u2061<\/mo><\/mrow><mo form=\"prefix\" stretchy=\"false\">(<\/mo><mi>a<\/mi><mo separator=\"true\">,<\/mo><mi>b<\/mi><mo form=\"postfix\" stretchy=\"false\">)<\/mo><mo form=\"postfix\" stretchy=\"false\">)<\/mo><\/mrow><annotation encoding=\"application\/x-tex\">O(\\log \\min(a,b))<\/annotation><\/semantics><\/math> )<br><strong>\u5e94\u7528<\/strong>\uff1a\u6c42 GCD \/ LCM<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">2. \u552f\u4e00\u5206\u89e3\u5b9a\u7406<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u6574\u6570\u4e0e\u8d28\u56e0\u6570\u7684\u53cc\u5c04\u5173\u7cfb<\/li>\n\n\n\n<li>\u5e94\u7528\uff1a\n<ul class=\"wp-block-list\">\n<li>\u7ea6\u6570\u4e2a\u6570\u516c\u5f0f\uff1a<math data-latex=\"d(n) = (k_1+1)(k_2+1)\\dots\"><semantics><mrow><mi>d<\/mi><mo form=\"prefix\" stretchy=\"false\">(<\/mo><mi>n<\/mi><mo form=\"postfix\" stretchy=\"false\">)<\/mo><mo>=<\/mo><mo form=\"prefix\" stretchy=\"false\">(<\/mo><msub><mi>k<\/mi><mn>1<\/mn><\/msub><mo>+<\/mo><mn>1<\/mn><mo form=\"postfix\" stretchy=\"false\">)<\/mo><mo form=\"prefix\" stretchy=\"false\">(<\/mo><msub><mi>k<\/mi><mn>2<\/mn><\/msub><mo>+<\/mo><mn>1<\/mn><mo form=\"postfix\" stretchy=\"false\">)<\/mo><mo>\u2026<\/mo><\/mrow><annotation encoding=\"application\/x-tex\">d(n) = (k_1+1)(k_2+1)\\dots<\/annotation><\/semantics><\/math><\/li>\n\n\n\n<li>\u7ea6\u6570\u548c\u516c\u5f0f\uff1a<math data-latex=\"\\sigma(n) = \\prod_{i}(1 + p_i + \\dots + p_i^{k_i})\"><semantics><mrow><mi>\u03c3<\/mi><mo form=\"prefix\" stretchy=\"false\">(<\/mo><mi>n<\/mi><mo form=\"postfix\" stretchy=\"false\">)<\/mo><mo>=<\/mo><msub><mo movablelimits=\"false\">\u220f<\/mo><mi>i<\/mi><\/msub><mo form=\"prefix\" stretchy=\"false\">(<\/mo><mn>1<\/mn><mo>+<\/mo><msub><mi>p<\/mi><mi>i<\/mi><\/msub><mo>+<\/mo><mo>\u22ef<\/mo><mo>+<\/mo><msubsup><mi>p<\/mi><mi>i<\/mi><msub><mi>k<\/mi><mi>i<\/mi><\/msub><\/msubsup><mo form=\"postfix\" stretchy=\"false\">)<\/mo><\/mrow><annotation encoding=\"application\/x-tex\">\\sigma(n) = \\prod_{i}(1 + p_i + \\dots + p_i^{k_i})<\/annotation><\/semantics><\/math><\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">3. \u57c3\u6c0f\u7b5b\uff08Eratosthenes\uff09<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>is_prime = &#91;True] * (n+1)\nis_prime&#91;0] = is_prime&#91;1] = False\nfor i in range(2, sqrt(n)+1):\n    if is_prime&#91;i]:\n        for j in range(i*i, n+1, i):\n            is_prime&#91;j] = False<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u590d\u6742\u5ea6<\/strong>\uff1a( <math data-latex=\"O(n \\log \\log n)\"><semantics><mrow><mi>O<\/mi><mo form=\"prefix\" stretchy=\"false\">(<\/mo><mi>n<\/mi><mrow><mspace width=\"0.1667em\"><\/mspace><mi>log<\/mi><mo>\u2061<\/mo><mspace width=\"0.1667em\"><\/mspace><\/mrow><mrow><mi>log<\/mi><mo>\u2061<\/mo><mspace width=\"0.1667em\"><\/mspace><\/mrow><mi>n<\/mi><mo form=\"postfix\" stretchy=\"false\">)<\/mo><\/mrow><annotation encoding=\"application\/x-tex\">O(n \\log \\log n)<\/annotation><\/semantics><\/math> )<br><strong>\u7279\u70b9<\/strong>\uff1a\u7b80\u5355\u3001\u7a7a\u95f4\u9002\u4e2d\u3001\u9002\u5408 n \u2264 1e7<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">4. \u7ebf\u6027\u7b5b\uff08\u6b27\u62c9\u7b5b\uff09<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>primes = &#91;]\nis_prime = &#91;True] * (n+1)\nfor i in range(2, n+1):\n    if is_prime&#91;i]:\n        primes.append(i)\n    for p in primes:\n        if i * p &gt; n: break\n        is_prime&#91;i * p] = False\n        if i % p == 0: break<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u590d\u6742\u5ea6<\/strong>\uff1a( <math data-latex=\"O(n) \"><semantics><mrow><mi>O<\/mi><mo form=\"prefix\" stretchy=\"false\">(<\/mo><mi>n<\/mi><mo form=\"postfix\" stretchy=\"false\">)<\/mo><\/mrow><annotation encoding=\"application\/x-tex\">O(n) <\/annotation><\/semantics><\/math>)<br><strong>\u7279\u70b9<\/strong>\uff1a\u6bcf\u4e2a\u5408\u6570\u53ea\u88ab\u6700\u5c0f\u8d28\u56e0\u5b50\u7b5b\u4e00\u6b21\uff0c\u9002\u5408 n \u2264 1e7~1e8<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">\u7d2f\u52a0\u7b26\u53f7 \u2211\uff08Sigma\uff09<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u542b\u4e49<\/strong>\uff1a\u628a\u4e00\u7cfb\u5217\u6570\u52a0\u8d77\u6765\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u4e00\u822c\u5f62\u5f0f<\/strong>\uff1a<math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><semantics><mrow><munderover><mo>\u2211<\/mo><mrow><mi>i<\/mi><mo>=<\/mo><mn>1<\/mn><\/mrow><mi>n<\/mi><\/munderover><msub><mi>a<\/mi><mi>i<\/mi><\/msub><mo>=<\/mo><msub><mi>a<\/mi><mn>1<\/mn><\/msub><mo>+<\/mo><msub><mi>a<\/mi><mn>2<\/mn><\/msub><mo>+<\/mo><mo>\u22ef<\/mo><mo>+<\/mo><msub><mi>a<\/mi><mi>n<\/mi><\/msub><\/mrow><\/semantics><\/math>\u200b<math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><semantics><mrow><msub><mi>a<\/mi><mi>i<\/mi><\/msub><\/mrow><\/semantics><\/math>\u662f\u901a\u9879\u516c\u5f0f<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><semantics><mrow><mi>i<\/mi><\/mrow><\/semantics><\/math>\u662f<strong>\u4e0b\u6807\u53d8\u91cf<\/strong>\uff08\u4ece\u4e0b\u754c\u5230\u4e0a\u754c\uff0c\u6bcf\u6b21 +1\uff09<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u7d2f\u4e58\u7b26\u53f7 \u220f\uff08Product\uff09<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u542b\u4e49<\/strong>\uff1a\u628a\u4e00\u7cfb\u5217\u6570\u4e58\u8d77\u6765\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u4e00\u822c\u5f62\u5f0f<\/strong>\uff1a<math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><semantics><mrow><munderover><mo>\u220f<\/mo><mrow><mi>i<\/mi><mo>=<\/mo><mn>1<\/mn><\/mrow><mi>n<\/mi><\/munderover><msub><mi>a<\/mi><mi>i<\/mi><\/msub><mo>=<\/mo><msub><mi>a<\/mi><mn>1<\/mn><\/msub><mo>\u00d7<\/mo><msub><mi>a<\/mi><mn>2<\/mn><\/msub><mo>\u00d7<\/mo><mo>\u22ef<\/mo><mo>\u00d7<\/mo><msub><mi>a<\/mi><mi>n<\/mi><\/msub><\/mrow><\/semantics><\/math>\u200b<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u4e00\u3001\u6982\u5ff5\u4e0e\u6027\u8d28\u68b3\u7406 1. \u7d20\u6570\u4e0e\u5408\u6570 2. \u6700\u5927\u516c\u7ea6\u6570\uff08GCD\uff09 3. \u6700\u5c0f\u516c\u500d\u6570\uff08LCM\uff09 4. \u540c\u4f59\u4e0e\u6a21\u8fd0 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[61],"tags":[],"class_list":["post-1520","post","type-post","status-publish","format-standard","hentry","category-zl"],"_links":{"self":[{"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/posts\/1520","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/comments?post=1520"}],"version-history":[{"count":2,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/posts\/1520\/revisions"}],"predecessor-version":[{"id":1522,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/posts\/1520\/revisions\/1522"}],"wp:attachment":[{"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/media?parent=1520"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/categories?post=1520"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/tags?post=1520"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}