\u8bbe $m$ \u4e3a\u6b63\u6574\u6570\uff0c\u5bf9\u4e8e\u6574\u6570 $a$ \uff0c\u82e5\u5b58\u5728\u6574\u6570 $x$ \u6ee1\u8db3\u540c\u4f59\u5f0f\uff1a<\/p>\n
$a \\cdot x \\equiv 1 \\pmod{m}$ <\/p>\n
\u5219\u79f0 $x$ \u4e3a $a$ \u5728\u6a21 $m$ \u4e0b\u7684\u4e58\u6cd5\u9006\u5143\uff0c\u8bb0\u4f5c $\\mathrm{inv}(a) \\pmod{m}$ \u3002<\/p>\n
\u6574\u6570 $a$ \u5728\u6a21 $m$ \u4e0b\u5b58\u5728\u4e58\u6cd5\u9006\u5143\u7684\u5145\u8981\u6761\u4ef6<\/strong>\u662f $\\gcd(a,m)=1$ \uff0c\u5373 $a$ \u4e0e $m$ \u4e92\u8d28\u3002<\/p>\n \u63a8\u8bba\uff1a\u82e5\u6a21\u6570 $p$ \u4e3a\u7d20\u6570\uff0c\u5219\u533a\u95f4 $[1,p-1]$ \u5185\u7684\u6240\u6709\u6574\u6570\u5747\u4e0e $p$ \u4e92\u8d28\uff0c\u5176\u6a21 $p$ \u9006\u5143\u5fc5\u7136\u5b58\u5728\u3002<\/p>\n \u82e5 $\\mathrm{inv}(b) \\pmod{m}$ \u5b58\u5728\uff08\u5373 $\\gcd(b,m)=1$ \uff09\uff0c\u5219\u6a21\u8fd0\u7b97\u4e2d\u7684\u9664\u6cd5\u53ef\u7b49\u4ef7\u8f6c\u5316\u4e3a\u6a21\u4e58\u6cd5\uff0c\u6ee1\u8db3\uff1a<\/p>\n $\\frac{a}{b} \\equiv a \\cdot \\mathrm{inv}(b) \\pmod{m}$ <\/p>\n \u8bc1\u660e\u6838\u5fc3\u57fa\u4e8e\u9006\u5143\u7684\u4e25\u683c\u5b9a\u4e49\u4e0e\u540c\u4f59\u5f0f\u7684\u57fa\u672c\u6027\u8d28\uff0c\u6b65\u9aa4\u5982\u4e0b\uff1a<\/p>\n \u7531\u9006\u5143\u7684\u5b9a\u4e49\uff081.1\u8282\uff09\uff0c\u56e0 $\\mathrm{inv}(b) \\pmod{m}$ \u5b58\u5728\uff0c\u6545\u6ee1\u8db3: $$ b \\cdot \\mathrm{inv}(b) \\equiv 1 \\pmod{m} \\tag{1}$$<\/p>\n<\/li>\n \u5b9a\u4e49\u6a21\u9664\u6cd5\u7684\u7b49\u4ef7\u5f62\u5f0f\uff1a\u8bbe $\\frac{a}{b} \\equiv c \\pmod{m}$ \uff08\u5176\u4e2d $c$ \u4e3a\u6574\u6570\uff09\uff0c\u6839\u636e\u540c\u4f59\u5f0f\u7684\u5b9a\u4e49\uff0c\u4e0a\u5f0f\u7b49\u4ef7\u4e8e\u201c\u5b58\u5728\u6574\u6570 $k$ \uff0c\u4f7f\u5f97 $a = b \\cdot c + k \\cdot m$ \u201d\uff08\u907f\u514d\u76f4\u63a5\u51fa\u73b0\u5206\u6570\u5f62\u5f0f\u7684\u6a21\u8fd0\u7b97\uff0c\u7b26\u5408\u6570\u8bba\u4e25\u8c28\u6027\uff09\u3002<\/p>\n<\/li>\n \u5bf9 $a = b \\cdot c + k \\cdot m$ \u4e24\u8fb9\u540c\u65f6\u53d6\u6a21 $m$ \uff0c\u6839\u636e\u6a21\u8fd0\u7b97\u201c\u548c\u7684\u6a21\u7b49\u4e8e\u6a21\u7684\u548c\u7684\u6a21\u201d\u6027\u8d28\uff0c\u4ee5\u53ca $k \\cdot m \\equiv 0 \\pmod{m}$ \uff0c\u5316\u7b80\u5f97\uff1a<\/p>\n $$a \\equiv b \\cdot c \\pmod{m} \\tag{2}$$ <\/p>\n<\/li>\n \u5bf9\u5f0f (2) \u4e24\u8fb9\u540c\u65f6\u4e58\u4ee5 $\\mathrm{inv}(b)$ \uff0c\u6839\u636e\u540c\u4f59\u5f0f\u7684\u4e58\u6cd5\u6027\u8d28\uff08\u82e5 $x \\equiv y \\pmod{m}$ \uff0c\u5219\u5bf9\u4efb\u610f\u6574\u6570 $z$ \uff0c\u6709 $x \\cdot z \\equiv y \\cdot z \\pmod{m}$ \uff09\uff0c\u53ef\u5f97\uff1a<\/p>\n<\/li>\n<\/ol>\n $$a \\cdot \\mathrm{inv}(b) \\equiv b \\cdot c \\cdot \\mathrm{inv}(b) \\pmod{m} \\tag{3}$$ <\/p>\n \u5c06\u5f0f (1) \u4ee3\u5165\u5f0f (3)\uff0c\u5229\u7528\u4e58\u6cd5\u7ed3\u5408\u5f8b\uff0c\u53f3\u8fb9\u5316\u7b80\u4e3a\uff1a<\/p>\n $$b \\cdot c \\cdot \\mathrm{inv}(b) = c \\cdot (b \\cdot \\mathrm{inv}(b)) \\equiv c \\cdot 1 \\equiv c \\pmod{m}$$<\/p>\n<\/li>\n \u7ed3\u5408\u6b65\u9aa42\u4e2d $\\frac{a}{b} \\equiv c \\pmod{m}$ \u7684\u5b9a\u4e49\uff0c\u53ef\u5f97\uff1a<\/p>\n $$a \\cdot \\mathrm{inv}(b) \\equiv \\frac{a}{b} \\pmod{m}$$ <\/p>\n<\/li>\n<\/ol>\n \u5373 $\\frac{a}{b} \\equiv a \\cdot \\mathrm{inv}(b) \\pmod{m}$ \uff0c\u63a8\u5bfc\u5b8c\u6bd5\u3002<\/p>\n \u4ec5\u8981\u6c42 $\\gcd(a,m)=1$ \uff0c\u5bf9\u6a21\u6570 $m$ \u65e0\u7d20\u6027\u8981\u6c42\uff0c\u662f\u6a21\u9006\u5143\u7684\u901a\u7528\u6c42\u89e3\u7b97\u6cd5<\/strong>\u3002<\/p>\n \u5bf9\u4efb\u610f\u6574\u6570 $a,b$ \uff0c\u5fc5\u7136\u5b58\u5728\u6574\u6570 $x,y$ \uff0c\u4f7f\u5f97\uff1a<\/p>\n $a \\cdot x + b \\cdot y = \\gcd(a,b)$ <\/p>\n \u8be5\u5b9a\u7406\u662f\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\u7684\u7406\u8bba\u57fa\u7840\u3002<\/p>\n \u9006\u5143\u7684\u5b9a\u4e49\u5f0f $a \\cdot x \\equiv 1 \\pmod{m}$ \u7b49\u4ef7\u4e8e\uff1a\u5b58\u5728\u6574\u6570 $y$ \uff0c\u4f7f\u5f97<\/p>\n $a \\cdot x - 1 = m \\cdot y$ <\/p>\n \u79fb\u9879\u540e\u5f97\u5230\u4e8c\u5143\u4e00\u6b21\u4e0d\u5b9a\u65b9\u7a0b\uff1a<\/p>\n $a \\cdot x + m \\cdot y = 1$ <\/p>\n \u7ed3\u5408\u9006\u5143\u5b58\u5728\u6027\u6761\u4ef6 $\\gcd(a,m)=1$ \uff0c\u8be5\u65b9\u7a0b\u7b26\u5408\u8d1d\u7956\u5b9a\u7406\u7684\u6709\u89e3\u6761\u4ef6\uff0c\u5176\u6574\u6570\u89e3 $x$ \u5373\u4e3a $a$ \u5728\u6a21 $m$ \u4e0b\u7684\u9006\u5143\u3002<\/p>\n \u666e\u901a\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\u7684\u6838\u5fc3\u662f\u8f97\u8f6c\u76f8\u9664\uff1a $\\gcd(a,b) = \\gcd(b, a \\bmod b)$ \u3002<\/p>\n \u8bbe\u5bf9\u4e8e $\\gcd(b, a \\bmod b)$ \uff0c\u5b58\u5728\u6574\u6570\u89e3 $x_1,y_1$ \u6ee1\u8db3\uff1a<\/p>\n $b \\cdot x_1 + (a \\bmod b) \\cdot y_1 = \\gcd(a,b)$ <\/p>\n \u7531\u5e26\u4f59\u9664\u6cd5\uff0c $a \\bmod b = a - \\lfloor \\frac{a}{b} \\rfloor \\cdot b$ \uff0c\u4ee3\u5165\u4e0a\u5f0f\u5f97\uff1a<\/p>\n $b \\cdot x_1 + \\left(a - \\lfloor \\frac{a}{b} \\rfloor \\cdot b\\right) \\cdot y_1 = \\gcd(a,b)$ <\/p>\n \u6574\u7406\u540e\u5f97\u5230\u539f\u65b9\u7a0b\u7684\u89e3\uff1a$\\begin{cases}x = y_1 \\\\ y = x_1 - \\lfloor \\frac{a}{b} \\rfloor \\cdot y_1 \\end{cases}$ <\/p>\n \u9012\u5f52\u7ec8\u6b62\u6761\u4ef6\u4e3a $b=0$ \uff0c\u6b64\u65f6 $\\gcd(a,0)=a$ \uff0c\u5bf9\u5e94\u89e3\u4e3a $x=1, y=0$ \u3002<\/p>\n \u7b97\u6cd5\u7684\u9012\u5f52\u6df1\u5ea6\u4e0e\u666e\u901a\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\u4e00\u81f4\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a $O(\\log \\min(a,m))$ \u3002<\/p>\n \u6a21\u6570 $p$ \u4e3a\u7d20\u6570\uff0c\u4e14 $\\gcd(a,p)=1$ \uff08\u5373 $a$ \u4e0d\u662f $p$ \u7684\u500d\u6570\uff09\u3002<\/p>\n \u82e5 $p$ \u4e3a\u7d20\u6570\uff0c\u4e14\u6574\u6570 $a$ \u4e0e $p$ \u4e92\u8d28\uff0c\u5219\uff1a<\/p>\n $a^{p-1} \\equiv 1 \\pmod{p}$ <\/p>\n \u5b9a\u4e49\u6a21 $p$ \u7684\u6700\u5c0f\u6b63\u7b80\u5316\u5269\u4f59\u7cfb $S = {1,2,\\dots,p-1}$ \uff0c\u8be5\u96c6\u5408\u6ee1\u8db3\uff1a<\/p>\n \u96c6\u5408\u5185\u6240\u6709\u5143\u7d20\u5747\u4e0e $p$ \u4e92\u8d28\uff1b<\/p>\n<\/li>\n \u4efb\u610f\u4e24\u4e2a\u5143\u7d20\u6a21 $p$ \u4e0d\u540c\u4f59\u3002<\/p>\n<\/li>\n<\/ol>\n \u6784\u9020\u65b0\u96c6\u5408 $S' = {a\\cdot1, a\\cdot2, \\dots, a\\cdot(p-1)}$ \uff0c\u4e0b\u8bc1 $S'$ \u6a21 $p$ \u540e\u662f $S$ \u7684\u4e00\u4e2a\u6392\u5217\uff1a<\/p>\n \u53cd\u8bc1\u6cd5\uff1a\u5047\u8bbe\u5b58\u5728 $i \\neq j$ \u4f7f\u5f97 $a\\cdot i \\equiv a\\cdot j \\pmod{p}$ \uff0c\u5219 $a(i-j) \\equiv 0 \\pmod{p}$ \u3002\u7531\u4e8e $\\gcd(a,p)=1$ \uff0c\u6545 $i-j \\equiv 0 \\pmod{p}$ \uff0c\u4e0e $i,j \\in [1,p-1]$ \u4e14 $i \\neq j$ \u77db\u76fe\u3002<\/p>\n<\/li>\n \u56e0\u6b64 $S'$ \u6a21 $p$ \u540e\u4e0e $S$ \u5305\u542b\u5b8c\u5168\u76f8\u540c\u7684\u5143\u7d20\uff0c\u4ec5\u987a\u5e8f\u4e0d\u540c\u3002<\/p>\n<\/li>\n<\/ul>\n \u5bf9\u4e24\u4e2a\u96c6\u5408\u7684\u6240\u6709\u5143\u7d20\u5206\u522b\u6c42\u4e58\u79ef\uff0c\u6a21 $p$ \u7ed3\u679c\u76f8\u7b49:<\/p>\n \u6574\u7406\u5f97\uff1a<\/p>\n $(p-1)! \\equiv a^{p-1} \\cdot (p-1)! \\pmod{p}$ <\/p>\n \u7531\u4e8e $p$ \u4e3a\u7d20\u6570\uff0c $\\gcd((p-1)!, p)=1$ \uff0c\u6545\u53ef\u5728\u540c\u4f59\u5f0f\u4e24\u8fb9\u7ea6\u53bb $(p-1)!$ \uff0c\u6700\u7ec8\u5f97\u5230\uff1a<\/p>\n $a^{p-1} \\equiv 1 \\pmod{p}$<\/p>\n \u8d39\u9a6c\u5c0f\u5b9a\u7406\u5f97\u8bc1\u3002<\/p>\n \u5c06\u8d39\u9a6c\u5c0f\u5b9a\u7406\u7684\u7ed3\u8bba\u62c6\u5206\u4e3a\uff1a<\/p>\n $a \\cdot a^{p-2} \\equiv 1 \\pmod{p}$ <\/p>\n \u5bf9\u6bd4\u9006\u5143\u7684\u5b9a\u4e49\u5f0f\uff0c\u76f4\u63a5\u5f97\u5230\u9006\u5143\u516c\u5f0f\uff1a<\/p>\n $\\mathrm{inv}(a) \\equiv a^{p-2} \\pmod{p}$ <\/p>\n \u9006\u5143\u516c\u5f0f\u7684\u6838\u5fc3\u662f\u5927\u6307\u6570\u6a21\u8fd0\u7b97\uff0c\u91c7\u7528\u5feb\u901f\u5e42\u7b97\u6cd5\u5b9e\u73b0\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a\u5bf9\u6570\u7ea7\u522b\u3002<\/p>\n \u5feb\u901f\u5e42\u7b97\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a $O(\\log p)$ \uff0c\u4e0e\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\u540c\u9636\uff0c\u4ee3\u7801\u5b9e\u73b0\u66f4\u7b80\u6d01\uff0c\u662f\u7d20\u6570\u6a21\u6570\u4e0b\u7684\u9996\u9009\u5355\u6b21\u9006\u5143\u6c42\u89e3\u65b9\u6848\u3002<\/p>\n \u6a21\u6570 $p$ \u4e3a\u7d20\u6570\uff0c\u9700\u8981\u6279\u91cf\u6c42\u89e3\u533a\u95f4 <\/strong> $[1,n]$ \uff08<\/strong> $n < p$ \uff09\u5185\u6240\u6709\u6574\u6570\u7684\u6a21 <\/strong> $p$ \u9006\u5143<\/strong>\u3002<\/p>\n \u5bf9\u4e8e\u7d20\u6570 $p$ \u548c\u4efb\u610f\u6574\u6570 $i \\in [2,p-1]$ \uff0c\u5bf9 $p$ \u548c $i$ \u505a\u5e26\u4f59\u9664\u6cd5\uff1a<\/p>\n $p = k \\cdot i + r, \\quad k = \\lfloor \\frac{p}{i} \\rfloor, \\quad 0 < r < i$ <\/p>\n \u5c06\u4e0a\u5f0f\u8f6c\u5316\u4e3a\u6a21 $p$ \u4e0b\u7684\u540c\u4f59\u5f0f\uff1a<\/p>\n $0 \\equiv k \\cdot i + r \\pmod{p}$ <\/p>\n \u79fb\u9879\u5f97\uff1a<\/p>\n $r \\equiv -k \\cdot i \\pmod{p}$ <\/p>\n \u7531\u4e8e $i,r \\in [1,p-1]$ \uff0c\u5176\u9006\u5143\u5fc5\u7136\u5b58\u5728\uff0c\u5728\u540c\u4f59\u5f0f\u4e24\u8fb9\u540c\u65f6\u4e58\u4ee5 $\\mathrm{inv}(i) \\cdot \\mathrm{inv}(r)$ \uff0c\u5f97\uff1a<\/p>\n $r \\cdot \\mathrm{inv}(i) \\cdot \\mathrm{inv}(r) \\equiv -k \\cdot i \\cdot \\mathrm{inv}(i) \\cdot \\mathrm{inv}(r) \\pmod{p}$ <\/p>\n \u5316\u7b80\u540e\u5f97\u5230\uff1a<\/p>\n $\\mathrm{inv}(i) \\equiv -k \\cdot \\mathrm{inv}(r) \\pmod{p}$ <\/p>\n \u5c06 $k = \\lfloor \\frac{p}{i} \\rfloor$ \u3001 $r = p % i$ \u4ee3\u5165\uff0c\u5e76\u5229\u7528\u6a21\u8fd0\u7b97\u6027\u8d28 $-x \\equiv p-x \\pmod{p}$ \u5c06\u8d1f\u53f7\u8f6c\u5316\u4e3a\u6b63\uff0c\u5f97\u5230\u6700\u7ec8\u9012\u63a8\u516c\u5f0f\uff1a<\/p>\n $\\mathrm{inv}(i) = \\left(p - \\lfloor \\frac{p}{i} \\rfloor\\right) \\cdot \\mathrm{inv}(p \\% i) \\% p$ <\/p>\n \u8fb9\u754c\u6761\u4ef6<\/strong>\uff1a $\\mathrm{inv}(1) = 1$ \uff0c\u53731\u7684\u6a21\u4efb\u610f\u6570\u9006\u5143\u5747\u4e3a1\u3002<\/p>\n \u6ce8\uff1a\u7531\u4e8e $r = p % i < i$ \uff0c\u9012\u63a8\u8fc7\u7a0b\u4e2d $\\mathrm{inv}(r)$ \u5df2\u5728\u4e4b\u524d\u7684\u6b65\u9aa4\u4e2d\u8ba1\u7b97\u5b8c\u6210\uff0c\u4fdd\u8bc1\u4e86\u9012\u63a8\u7684\u53ef\u884c\u6027\u3002<\/p>\n \u7b97\u6cd5\u4ec5\u9700\u4e00\u6b21\u904d\u5386\u5373\u53ef\u5b8c\u6210\u533a\u95f4\u5185\u6240\u6709\u9006\u5143\u7684\u6c42\u89e3\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a $O(n)$ \uff0c\u662f\u6279\u91cf\u6c42\u89e3\u9006\u5143\u7684\u6700\u4f18\u590d\u6742\u5ea6\uff0c\u663e\u8457\u4f18\u4e8e $n$ \u6b21\u5355\u6b21\u6c42\u89e3\u7684 $O(n \\log p)$ \u590d\u6742\u5ea6\u3002<\/p>\n \u9006\u5143\u7684\u4e09\u79cd\u6838\u5fc3\u6c42\u89e3\u7b97\u6cd5\uff1a\u539f\u7406\u3001\u8bc1\u660e\u4e0e\u5b9e\u73b0 \u524d\u7f6e\u5b9a\u4e49\u4e0e\u6838\u5fc3\u5b9a\u7406 \u6a21\u4e58\u6cd5\u9006\u5143\u7684\u4e25\u683c\u5b9a\u4e49 \u8bbe $m$ \u4e3a\u6b63\u6574\u6570\uff0c\u5bf9\u4e8e […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[],"class_list":["post-840","post","type-post","status-publish","format-standard","hentry","category-science-and-engineering"],"_links":{"self":[{"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/posts\/840","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/vite66.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=840"}],"version-history":[{"count":41,"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/posts\/840\/revisions"}],"predecessor-version":[{"id":921,"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/posts\/840\/revisions\/921"}],"wp:attachment":[{"href":"https:\/\/vite66.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=840"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/vite66.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=840"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/vite66.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=840"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\u6838\u5fc3\u5e94\u7528\u6027\u8d28<\/h3>\n
\u6027\u8d28\u63a8\u5bfc\uff08\u4e25\u683c\u6570\u5b66\u8bc1\u660e\uff09<\/h4>\n
\n
\n
\n\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\u6c42\u89e3\u9006\u5143<\/h2>\n
\u9002\u7528\u6761\u4ef6<\/h3>\n
\u6570\u5b66\u539f\u7406\u4e0e\u8bc1\u660e<\/h3>\n
\u8d1d\u7956\u5b9a\u7406<\/h4>\n
\u540c\u4f59\u5f0f\u5230\u4e0d\u5b9a\u65b9\u7a0b\u7684\u7b49\u4ef7\u8f6c\u5316<\/h4>\n
\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\u7684\u9012\u5f52\u63a8\u5bfc<\/h4>\n
\u7b97\u6cd5\u5b9e\u73b0<\/h3>\n
\n#include <iostream>\nusing namespace std;\ntypedef long long ll;\n\n\/**\n * @brief \u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\n * @param a \u6574\u6570a\n * @param b \u6574\u6570b\n * @param x \u5f15\u7528\u8fd4\u56de\u8d1d\u7956\u65b9\u7a0b\u7684\u89e3x\n * @param y \u5f15\u7528\u8fd4\u56de\u8d1d\u7956\u65b9\u7a0b\u7684\u89e3y\n * @return gcd(a,b)\n *\/\nll exgcd(ll a, ll b, ll &x, ll &y) {\n if (b == 0) {\n x = 1;\n y = 0;\n return a;\n }\n ll g = exgcd(b, a % b, y, x);\n y -= a \/ b * x;\n return g;\n}\n\n\/**\n * @brief \u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u6cd5\u6c42\u89e3\u6a21\u9006\u5143\n * @param a \u5f85\u6c42\u9006\u5143\u7684\u6574\u6570a\n * @param m \u6a21\u6570m\n * @return \u82e5\u9006\u5143\u5b58\u5728\uff0c\u8fd4\u56de\u6a21m\u7684\u6700\u5c0f\u975e\u8d1f\u9006\u5143\uff1b\u5426\u5219\u8fd4\u56de-1\n *\/\nll mod_inv_exgcd(ll a, ll m) {\n ll x, y;\n ll g = exgcd(a, m, x, y);\n if (g != 1) return -1; \/\/ \u4e0d\u4e92\u8d28\uff0c\u9006\u5143\u4e0d\u5b58\u5728\n return (x % m + m) % m; \/\/ \u5c06\u89e3\u6620\u5c04\u5230\u6a21m\u7684\u6700\u5c0f\u975e\u8d1f\u5269\u4f59\u7cfb\n}<\/code><\/pre>\n\u590d\u6742\u5ea6\u5206\u6790<\/h3>\n
\n\u8d39\u9a6c\u5c0f\u5b9a\u7406\u6cd5\u6c42\u89e3\u9006\u5143<\/h2>\n
\u9002\u7528\u6761\u4ef6<\/h3>\n
\u6570\u5b66\u539f\u7406\u4e0e\u8bc1\u660e<\/h3>\n
\u8d39\u9a6c\u5c0f\u5b9a\u7406<\/h4>\n
\u8d39\u9a6c\u5c0f\u5b9a\u7406\u7684\u4e25\u8c28\u8bc1\u660e<\/h4>\n
\n
\n
\\prod_{k=1}^{p-1}k \\equiv \\prod_{k=1}^{p-1} (a\\cdot k) \\pmod{p}<\/code><\/pre>\n\u9006\u5143\u516c\u5f0f\u63a8\u5bfc<\/h4>\n
\u7b97\u6cd5\u5b9e\u73b0<\/h3>\n
\n#include <iostream>\nusing namespace std;\ntypedef long long ll;\n\n\/**\n * @brief \u5feb\u901f\u5e42\u7b97\u6cd5\uff1a\u8ba1\u7b97 (base^exponent) % mod\n * @param base \u5e95\u6570\n * @param exponent \u6307\u6570\n * @param mod \u6a21\u6570\n * @return \u6a21\u8fd0\u7b97\u7ed3\u679c\n *\/\nll qpow(ll base, ll exponent, ll mod) {\n ll res = 1;\n base %= mod;\n while (exponent > 0) {\n if (exponent & 1) res = res * base % mod;\n base = base * base % mod;\n exponent >>= 1;\n }\n return res;\n}\n\n\/**\n * @brief \u8d39\u9a6c\u5c0f\u5b9a\u7406\u6cd5\u6c42\u89e3\u6a21\u9006\u5143\n * @param a \u5f85\u6c42\u9006\u5143\u7684\u6574\u6570a\n * @param p \u7d20\u6570\u6a21\u6570p\n * @return \u82e5\u9006\u5143\u5b58\u5728\uff0c\u8fd4\u56de\u6a21p\u7684\u6700\u5c0f\u975e\u8d1f\u9006\u5143\uff1b\u5426\u5219\u8fd4\u56de-1\n *\/\nll mod_inv_fermat(ll a, ll p) {\n if (a % p == 0) return -1; \/\/ a\u662fp\u7684\u500d\u6570\uff0c\u9006\u5143\u4e0d\u5b58\u5728\n return qpow(a, p - 2, p);\n}<\/code><\/pre>\n\u590d\u6742\u5ea6\u5206\u6790<\/h3>\n
\n\u7ebf\u6027\u9012\u63a8\u6cd5\u6c42\u89e3\u9006\u5143<\/h2>\n
\u9002\u7528\u6761\u4ef6<\/h3>\n
\u6570\u5b66\u539f\u7406\u4e0e\u63a8\u5bfc<\/h3>\n
\u7b97\u6cd5\u5b9e\u73b0<\/h3>\n
\n#include <iostream>\nusing namespace std;\ntypedef long long ll;\n\nconst int MAXN = 1e6 + 10; \/\/ \u6309\u9700\u8c03\u6574\u6570\u7ec4\u4e0a\u9650\nll inv[MAXN];\n\n\/**\n * @brief \u7ebf\u6027\u9012\u63a8\u6cd5\u6279\u91cf\u6c42\u89e3\u6a21\u9006\u5143\n * @param n \u6c42\u89e3\u533a\u95f4[1,n]\u7684\u9006\u5143\n * @param p \u7d20\u6570\u6a21\u6570p\n *\/\nvoid mod_inv_linear(int n, ll p) {\n inv[1] = 1; \/\/ \u8fb9\u754c\u6761\u4ef6\n for (int i = 2; i <= n; ++i) {\n inv[i] = (p - p \/ i) * inv[p % i] % p;\n }\n}<\/code><\/pre>\n\u590d\u6742\u5ea6\u5206\u6790<\/h3>\n
\n\u7b97\u6cd5\u9009\u578b\u603b\u7ed3<\/h2>\n
\n\n
\n \n\u7b97\u6cd5<\/th>\n \u6a21\u6570\u8981\u6c42<\/th>\n \u6838\u5fc3\u9002\u7528\u573a\u666f<\/th>\n \u65f6\u95f4\u590d\u6742\u5ea6<\/th>\n \u4f18\u52bf<\/th>\n<\/tr>\n<\/thead>\n \n \u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5<\/td>\n \u65e0\u7d20\u6027\u8981\u6c42\uff0c\u4ec5\u9700 $\\gcd(a,m)=1$<\/td>\n \u901a\u7528\u573a\u666f\u3001\u975e\u7d20\u6570\u6a21\u6570\u4e0b\u5355\u6b21\u9006\u5143\u6c42\u89e3<\/td>\n $O(\\log \\min(a,m))$<\/td>\n \u901a\u7528\u6027\u6700\u5f3a\uff0c\u65e0\u7d20\u6570\u7ea6\u675f<\/td>\n<\/tr>\n \n \u8d39\u9a6c\u5c0f\u5b9a\u7406\u6cd5<\/td>\n \u5fc5\u987b\u4e3a\u7d20\u6570\uff0c\u4e14 $\\gcd(a,p)=1$<\/td>\n \u7d20\u6570\u6a21\u6570\u4e0b\u5355\u6b21\u9006\u5143\u6c42\u89e3<\/td>\n $O(\\log p)$<\/td>\n \u4ee3\u7801\u7b80\u6d01\uff0c\u5b9e\u73b0\u6210\u672c\u4f4e\uff0c\u7ade\u8d5b\u573a\u666f\u9996\u9009<\/td>\n<\/tr>\n \n \u7ebf\u6027\u9012\u63a8\u6cd5<\/td>\n \u5fc5\u987b\u4e3a\u7d20\u6570\uff0c\u4e14\u6c42\u89e3\u533a\u95f4 $[1,n] < p$<\/td>\n \u7d20\u6570\u6a21\u6570\u4e0b\u6279\u91cf\u6c42\u89e3\u533a\u95f4\u9006\u5143<\/td>\n $O(n)$<\/td>\n \u6279\u91cf\u6c42\u89e3\u6548\u7387\u6700\u4f18\uff0c\u9002\u5408\u7ec4\u5408\u6570\u3001DP\u7b49\u5927\u89c4\u6a21\u9006\u5143\u5e94\u7528\u573a\u666f<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
\n","protected":false},"excerpt":{"rendered":"