{"id":1170,"date":"2023-02-10T12:01:46","date_gmt":"2023-02-10T04:01:46","guid":{"rendered":"http:\/\/www.algmain.com\/?page_id=1170"},"modified":"2023-02-11T12:29:36","modified_gmt":"2023-02-11T04:29:36","slug":"hash-theory","status":"publish","type":"page","link":"http:\/\/www.algmain.com\/index.php\/algorithm-article\/hashtree\/hash-theory\/","title":{"rendered":"\u7406\u8bba\u57fa\u7840"},"content":{"rendered":"\n

\u4f9d\u636e\u54c8\u5e0c\u51fd\u6570\u6784\u5efa\u7684\u67e5\u627e\u7b97\u6cd5\u88ab\u79f0\u4e3a\u54c8\u5e0c\u7b97\u6cd5\u3002\u672c\u6587\u524d\u9762\u5df2\u7ecf\u5f52\u7eb3\u548c\u603b\u7ed3\u8fc7\uff1a\u54c8\u5e0c\u51fd\u6570\u53ef\u4ee5\u7b80\u5316\u548c\u5f52\u7eb3\u4e3a\u5546\u6570\u7c7b\u54c8\u5e0c\u51fd\u6570\u548c\u4f59\u6570\u7c7b\u54c8\u5e0c\u51fd\u6570\u3002\u90a3\u4e48\u6784\u5efa\u54c8\u5e0c\u7b97\u6cd5\uff0c\u4e5f\u5c31\u4e3b\u8981\u5728\u8fd9\u4e24\u7c7b\u51fd\u6570\u4e2d\u9009\u62e9\u6216\u7531\u8fd9\u4e24\u7c7b\u51fd\u6570\u6d3e\u751f\u3002\u53e6\u5916\u5bf9\u4e8e\u54c8\u5e0c\u51fd\u6570\u7684\u8bc4\u4ef7\u65b9\u5f0f\uff0c\u540c\u6837\u9002\u7528\u4e8e\u54c8\u5e0c\u7b97\u6cd5\uff0c\u5305\u62ec\u5206\u8fa8\u80fd\u529b\u548c\u51b2\u7a81\u6982\u7387\u3002<\/p>\n\n\n\n

\u672c\u8282\u4e2d\u5148\u8865\u5145\u524d\u9762\u5bf9\u4f59\u6570\u7c7b\u54c8\u5e0c\u51fd\u6570\u5206\u8fa8\u80fd\u529b\\(D\\)\u7684\u8ba1\u7b97\uff0c\u7136\u540e\u5bf9\u6bd4\u4e24\u7c7b\u51fd\u6570\u7684\u4f18\u7f3a\u70b9\uff0c\u6700\u540e\u8bf4\u660e\u54c8\u5e0c\u7b97\u6cd5\u7684\u57fa\u672c\u6784\u5efa\u601d\u8def\u3002<\/p>\n\n\n\n

1 \u8d28\u6570\u5206\u8fa8\u5b9a\u7406<\/h2>\n\n\n\n

\u5b9a\u74067<\/strong>\uff1a\u9009\u53d6\u4efb\u610f\u4e2a\u4e92\u4e0d\u76f8\u540c\u7684\u8d28\u6570\uff1a\\(P_1<P_2<P_3<\u2026\u2026<P_{n\u22121}<P_n\\)\uff08\\(n\u2208N^\u2217\\)\uff09\uff0c\u5b9a\u4e49\uff1a\\(M = \\prod\\limits_{i = 1}^n {P_i}=P_1\\times P_2\\times P_3\\times \u2026\u2026\\times P_{n\u22121}\\times P_n\\)<\/p>\n\n\n\n

\u8bbe\\(m\u2264k_1<k_2<m+M\\)\uff08\\(m,k_1,k_2\u2208N\\)\u00a0\uff09\uff0c\u90a3\u4e48\u5bf9\u4e8e\u4efb\u610f\u7684\uff0c\\(i\u2208[1,n]\\)\uff08\\(k_1\\,mod\\,P_i\\)\uff09\uff1d\uff08\\(k_2\\,mod\\,P_i\\)\uff09\u4e0d\u53ef\u80fd\u603b\u6210\u7acb\u3002<\/p>\n\n\n\n

\u8bc1\u660e<\/strong>\uff1a\u5047\u8bbe\u5b9a\u74067\u7684\u7ed3\u8bba\u4e0d\u6b63\u786e\uff0c\u90a3\u4e48\u5bf9\u4e8e\u4efb\u610f\u7684\uff0c\\(i\u2208[1,n]\\)\u00a0\uff08\\(k_1\\,mod\\,P_i\\)\u00a0\uff09\uff1d\uff08\\(k_2\\,mod\\,P_i\\)\u00a0\uff09\u5c06\u603b\u662f\u6210\u7acb\u3002\u8fd9\u4e2a\u53ef\u4ee5\u8868\u8fbe\u4e3a\uff1a\u00a0<\/p>\n\n\n\n

\\[ k_1 = s_{1i} \\times P_i + r_i,\\, k_2 = s_{2i} \\times P_i + r_i \\quad (s_{1i}, s_{2i}, r_i \\in N) \\]<\/p>\n\n\n\n

\u8bbe\uff1a\\(K = k_2 – k_1 = (s_{2i} – s_{1i}) \\times P_i \\ne 0\\)<\/p>\n\n\n\n

\u663e\u7136\uff0c\\(K\\)\u662f\u4e00\u4e2a\u5408\u6570\uff0c\u800c\u4e14\u5305\u542b\u8d28\u56e0\u6570\\(P_i\\)\u3002\u6839\u636e\u8d28\u6570\u7684\u5b9a\u4e49\u548c\u8d28\u56e0\u6570\u5206\u89e3\u5b9a\u7406\uff0c\\(K\\)\u53ef\u4ee5\u8868\u8fbe\u4e3a\uff1a<\/p>\n\n\n\n

\\[K = P_1\\times P_2\\times P_3\\times \u2026\u2026\\times P_{n\u22121}\\times P_n \\times S \\ge M \\quad (S \\in N^*) \\]<\/p>\n\n\n\n

\u800c\u53e6\u5916\u4e00\u65b9\u9762\uff0c\u6839\u636e\\(m \\le k_1 < k_2 < m+M\\)\uff0c\u53ef\u4ee5\u5f97\u51fa\\(0 < k_2 – k_1 < M \\)<\/p>\n\n\n\n

\u5f88\u660e\u663e\uff0c\u8fd9\u4e24\u4e2a\u7ed3\u8bba\u662f\u76f8\u4e92\u77db\u76fe\u7684\u3002\u56e0\u6b64\u539f\u5b9a\u74067\u6b63\u786e\u3002<\/p>\n\n\n\n

\u8fd9\u4e2a\u5b9a\u74067\u53ef\u4ee5\u7b80\u5355\u7684\u8868\u8ff0\u4e3a\uff1a\u4e2a\u4e0d\u540c\u7684\u8d28\u6570\u53ef\u4ee5”\u5206\u8fa8”\u7684\u8fde\u7eed\u6574\u6570\u7684\u4e2a\u6570\u548c\u4ed6\u4eec\u7684\u4e58\u79ef\u76f8\u7b49\u3002”\u5206\u8fa8”\u5c31\u662f\u6307\u8fd9\u4e9b\u8fde\u7eed\u7684\u6574\u6570\u4e0d\u53ef\u80fd\u6709\u5b8c\u5168\u76f8\u540c\u7684\u4f59\u6570\u5e8f\u5217\u3002<\/p>\n\n\n\n

2 \u4f59\u6570\u5206\u8fa8\u5b9a\u7406<\/h2>\n\n\n\n

\u5728\u8fd9\u91cc\uff0c\u5bf9\u66f4\u4e3a\u666e\u904d\u7684\u4f59\u6570\u5206\u8fa8\u65b9\u5f0f\u505a\u4e00\u4e2a\u8bba\u8ff0\u3002<\/p>\n\n\n\n

\u5b9a\u74068<\/strong>\uff1a\u9009\u53d6\u4efb\u610f\u4e2a\u4e92\u4e0d\u76f8\u540c\u7684\u81ea\u7136\u6570\uff1a\\(\u00a0I_1<I_2<I_3<\u2026\u2026<I_{n\u22121}<I_n\\)\uff08\\(n\u2208N^\u2217\\)\uff09\uff0c\u5b9a\u4e49LCM\uff08Lease Common Multiple\uff09\u4e3a\u7684\u6700\u5c0f\u516c\u500d\u6570\u3002<\/p>\n\n\n\n

\u8bbe\\(m\u2264k_1<k_2<m+LCM\\)\uff08\\(m,k_1,k_2\u2208N\\)\uff09\uff0c\u90a3\u4e48\u5bf9\u4e8e\u4efb\u610f\u7684\\(i\u2208[1,n]\\)\u00a0\uff0c\uff08\\(k_1\\,mod\\, I_i\\)\uff09\uff1d\uff08\\(k_2\\,mod\\, I_i\\)\uff09\u4e0d\u53ef\u80fd\u603b\u6210\u7acb\u3002<\/p>\n\n\n\n

\u8bc1\u660e\uff1a\u5047\u8bbe\u5b9a\u74068\u7684\u7ed3\u8bba\u4e0d\u6b63\u786e\uff0c\u90a3\u4e48\u5bf9\u4e8e\u4efb\u610f\u7684\\(i \\in [1,n]\\)\uff0c\uff08\\(k_1\\,mod\\, I_i\\)\uff09\uff1d\uff08\\(k_2\\,mod\\, I_i\\)\uff09\u5c06\u603b\u662f\u6210\u7acb\u3002\u8fd9\u4e2a\u53ef\u4ee5\u8868\u8fbe\u4e3a\uff1a<\/p>\n\n\n\n

\\[ k_1 = s_{1i} \\times I_i + r_i,\\, k_2 = s_{2i} \\times I_i + r_i \\quad (s_{1i}, s_{2i}, r_i \\in N) \\]<\/p>\n\n\n\n

\u8bbe\uff1a\\(K = k_2 – k_1 = (s_{2i} – s_{1i}) \\times I_i \\ne 0\\)<\/p>\n\n\n\n

\u663e\u7136\uff0c\\(K\\)\u662f\u4e00\u4e2a\u5408\u6570\uff0c\u800c\u4e14\u5305\u542b\u56e0\u7d20\\(I_i\\)\u3002\u6839\u636e\u6700\u5c0f\u516c\u500d\u6570\u7684\u5b9a\u4e49\uff0c\u53ef\u4ee5\u8868\u8fbe\u4e3a\uff1a<\/p>\n\n\n\n

\\[K=k_2-k_1 = S \\times LCM \\ge LCM \\quad (S \\in N^*) \\]<\/p>\n\n\n\n

\u800c\u53e6\u5916\u4e00\u65b9\u9762\uff0c\u6839\u636e\\(m \\le k_1 < k_2 < m+LCM\\)\uff0c\u53ef\u4ee5\u5f97\u51fa\\(0 < k_2 – k_1 < LCM \\)<\/p>\n\n\n\n

\u5f88\u660e\u663e\uff0c\u8fd9\u4e24\u4e2a\u7ed3\u8bba\u662f\u76f8\u4e92\u77db\u76fe\u7684\u3002\u56e0\u6b64\u539f\u5b9a\u74068\u6b63\u786e\u3002<\/p>\n\n\n\n

\u8fd9\u4e2a\u5b9a\u74068\u53ef\u4ee5\u7b80\u5355\u7684\u8868\u8ff0\u4e3a\uff1a\u4e2a\u4e0d\u540c\u7684\u6570\u53ef\u4ee5”\u5206\u8fa8”\u7684\u8fde\u7eed\u6574\u6570\u7684\u4e2a\u6570\u4e0d\u8d85\u8fc7\u4ed6\u4eec\u7684\u6700\u5c0f\u516c\u500d\u6570\u3002\u5b9a\u74067\u662f\u5b9a\u74068\u7684\u4e00\u4e2a\u7279\u4f8b\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"

\u4f9d\u636e\u54c8\u5e0c\u51fd\u6570\u6784\u5efa\u7684\u67e5\u627e\u7b97\u6cd5\u88ab\u79f0\u4e3a\u54c8\u5e0c\u7b97\u6cd5\u3002\u672c\u6587\u524d\u9762\u5df2\u7ecf\u5f52\u7eb3\u548c\u603b\u7ed3\u8fc7\uff1a\u54c8\u5e0c\u51fd\u6570\u53ef\u4ee5\u7b80\u5316\u548c\u5f52\u7eb3\u4e3a\u5546\u6570\u7c7b\u54c8\u5e0c\u51fd\u6570\u548c\u4f59 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":754,"menu_order":1,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1170","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"http:\/\/www.algmain.com\/index.php\/wp-json\/wp\/v2\/pages\/1170"}],"collection":[{"href":"http:\/\/www.algmain.com\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"http:\/\/www.algmain.com\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"http:\/\/www.algmain.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.algmain.com\/index.php\/wp-json\/wp\/v2\/comments?post=1170"}],"version-history":[{"count":16,"href":"http:\/\/www.algmain.com\/index.php\/wp-json\/wp\/v2\/pages\/1170\/revisions"}],"predecessor-version":[{"id":1327,"href":"http:\/\/www.algmain.com\/index.php\/wp-json\/wp\/v2\/pages\/1170\/revisions\/1327"}],"up":[{"embeddable":true,"href":"http:\/\/www.algmain.com\/index.php\/wp-json\/wp\/v2\/pages\/754"}],"wp:attachment":[{"href":"http:\/\/www.algmain.com\/index.php\/wp-json\/wp\/v2\/media?parent=1170"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}