- \n
- \n
\u9898\u76ee\u63cf\u8ff0<\/strong><\/h3>\n<\/li>\n<\/ul>\n
\u5b9a\u4e49\u6a21\u610f\u4e49\u4e0b\u7684\u9012\u63a8\u6570\u5217 \\(\\displaystyle f_n=\\left\\{ {\\begin{array}{*{20}{c}} 1&{,n \\le 2}\\\\ {{f_{n – 1}} + {f_{n – 2}}}&{,n > 2} \\end{array}} \\right.\\)\uff0c\u5176\u4e2d\u6a21\u6570\u4e3a \\(1000000009\\) \u3002<\/p>\n
\u7ed9\u5b9a\u6574\u6570 \\(c\\)\uff08\\(0 \\leq c < 1000000009\\)\uff09\uff0c\u6c42\u51fa\u5b83\u6700\u65e9\u51fa\u73b0\u5728\u6570\u5217\u7684\u54ea\u4e2a\u4f4d\u7f6e\uff0c\u5e76\u8f93\u51fa\u4e0b\u6807\u3002<\/p>\n
\u82e5 \\(c\\) \u6c38\u8fdc\u4e0d\u4f1a\u51fa\u73b0\u5728\u6b64\u6570\u5217\u7684\u4efb\u4e00\u4f4d\u7f6e\uff0c\u5219\u8f93\u51fa \\(-1\\) \u3002<\/p>\n
- \n
- \n
\u8f93\u5165\u683c\u5f0f<\/strong><\/h3>\n<\/li>\n<\/ul>\n
\u591a\u7ec4\u6570\u636e\u3002<\/p>\n
\u7b2c\u4e00\u884c\u4e00\u4e2a\u6b63\u6574\u6570 \\(T\\) \uff08\\(0 < T \\leq 100\\)\uff09 \u8868\u793a \\(T\\) \u7ec4\u6570\u636e\u3002<\/p>\n
\u63a5\u4e0b\u6765 \\(T\\) \u884c\u6bcf\u884c\u4e00\u4e2a\u6570\u8868\u793a\u6bcf\u7ec4\u6570\u636e\u7684 \\(c\\) \u3002<\/p>\n
- \n
- \n
\u8f93\u51fa\u683c\u5f0f<\/strong><\/h3>\n<\/li>\n<\/ul>\n
\u5bf9\u4e8e\u6bcf\u7ec4\u6570\u636e\uff0c\u8f93\u51fa\u4e00\u884c\u4e00\u4e2a\u6570\u8868\u793a\u7b54\u6848\u3002<\/p>\n
- \n
- \n
\u6837\u4f8b\u8f93\u5165<\/strong><\/h3>\n<\/li>\n<\/ul>\n
2\r\n987\r\n321<\/pre>\n
- \n
- \n
\u6837\u4f8b\u8f93\u51fa<\/strong><\/h3>\n<\/li>\n<\/ul>\n
16\r\n-1<\/pre>\n
<\/p>\n
<\/p>\n
<\/p>\n
Source\uff1a BZOJ 5104<\/p>\n
<\/p>\n
\n<\/p>\n
<\/p>\n
<\/p>\n
\u5728\u5176\u4ed6\u5730\u65b9\u5077\u5077\u85cf\u4e86\u70b9\u79c1\u8d27www\uff0c\u7136\u800c\u8fd9\u91cc\u6ca1\u6709
\uff08\u4e0d\u9700\u8981\u85cf\uff09<\/del><\/p>\n<\/p>\n
\u7b80\u7ea6\u6982\u8ff0\uff1a\u6709\u516c\u5f0f \\(\\displaystyle f_n=\\frac{1}{\\sqrt5}\\left(\\frac{1+\\sqrt5}{2}\\right)^n – \\frac{1}{\\sqrt5}\\left(\\frac{1-\\sqrt5}{2}\\right)^n\\) \uff0c\u53ef\u4ee5\u5957\u7528 BSGS \u4ee5\u53ca Cipolla \u89e3\u51fa \\(n\\) \u3002<\/p>\n
\u6781\u81f4\u5185\u5bb9\uff1a<\/p>\n
- \n
- \n
Section A<\/h3>\n<\/li>\n<\/ul>\n
\u9996\u5148\uff0c\\(f_n\\) \u7684\u901a\u9879\u516c\u5f0f\u53ef\u4ee5\u901a\u8fc7\u7b80\u5355\u7684\u6570\u5b66\u6784\u9020\u5f97\u5230\u3002<\/p>\n
\u56e0\u4e3a\u4e00\u9636\u7ebf\u6027\u5e38\u7cfb\u6570\u9f50\u6b21\u9012\u63a8\u7684\u901a\u9879\u516c\u5f0f\u4e3a\u7b49\u6bd4\u6570\u5217\uff0c\u6240\u4ee5\u540c\u7406\u8bbe \\(t, q\\)\uff0c\u4f7f\u5f97 \\(\\displaystyle f_n-tf_{n-1} = q\\left(f_{n-1}-tf_{n-2}\\right)\\) \u3002<\/p>\n
\u5c55\u5f00\u6574\u7406\u5f97 \\(\\displaystyle f_n = \\left(q+t\\right)f_{n-1}-qtf_{n-2}\\) \uff0c\u5373 \\(\\displaystyle \\left\\{ {\\begin{array}{*{20}{c}}{q + t = 1}\\\\{qt =\u00a0 – 1}\\end{array}} \\right.\\) \u3002<\/p>\n
\u6784\u9020\u4e8c\u6b21\u51fd\u6570 \\(x^2-x-1=0\\) \uff0c\u7531\u97e6\u8fbe\u5b9a\u7406\u53ef\u77e5 \\(q, t\\) \u5206\u522b\u4e3a\u6b64\u65b9\u7a0b\u4e24\u6839\uff0c\u5373 \\(\\displaystyle \\frac{1+\\sqrt5}{2}\\) \u6216 \\(\\displaystyle \\frac{1-\\sqrt5}{2}\\) \u3002<\/p>\n
\u7136\u540e\u5957\u5f88\u591a\u4e2a\u7b49\u6bd4\u6570\u5217\u6c42\u548c\u516c\u5f0f\uff0c\u6216\u8005\u76f4\u63a5\u8bbe \\(\\displaystyle f_n = ax_1^n + bx_2^n\\) \u4ee3\u5165\u7279\u6b8a\u503c\u89e3\u65b9\u7a0b\u7ec4\uff0c\u90fd\u53ef\u4ee5\u5f97\u51fa\u00a0\\(\\displaystyle f_n=\\frac{1}{\\sqrt5}\\left(\\frac{1+\\sqrt5}{2}\\right)^n – \\frac{1}{\\sqrt5}\\left(\\frac{1-\\sqrt5}{2}\\right)^n\\) \u3002<\/p>\n
<\/p>\n
- \n
- \n
Section B<\/span><\/h3>\n<\/li>\n<\/ul>\n
\u63a5\u4e0b\u6765\u5bf9\u8fd9\u4e2a\u516c\u5f0f\u8fdb\u884c\u4e00\u70b9\u5904\u7406\u3002<\/p>\n
\u8bbe \\(c=f_n\\)\uff0c\\(\\displaystyle t=\\frac{1+\\sqrt5}{2}\\) \uff0c\u5219\u53ef\u77e5 \\(\\displaystyle \\frac{1-\\sqrt5}{2} = -\\frac{1}{t}\\)<\/span> \uff0c\u6240\u4ee5\u6709\uff1a \\(\\displaystyle \\sqrt 5 c = {\\left( t \\right)^n} – {\\left( { – {1 \\over t}} \\right)^n}\\) \u3002<\/p>\n
\u6362\u5143\uff0c\u518d\u8bbe \\(x=t^n\\) \uff0c\u5219\u6709\uff1a\u00a0\\(\\displaystyle \\sqrt 5 c = x – {\\left( { – 1} \\right)^n}\\frac{1}{x}\\) \u3002<\/p>\n
\u518d\u6574\u7406\uff0c\u53ef\u5f97\u4ee5 \\(x\\) \u4e3a\u4e3b\u5143\u7684\u4e00\u5143\u4e8c\u6b21\u65b9\u7a0b \\(\\displaystyle x^2 – \\sqrt5cx – {\\left( { – 1} \\right)^n} = 0\\) \u3002<\/p>\n
\u6b64\u65b9\u7a0b \\(\\displaystyle \\Delta = 5c^2 + 4\\left( { – 1} \\right)^n\\) \uff0c\u7136\u540e\u5957\u7528\u4e00\u5143\u4e8c\u6b21\u65b9\u7a0b\u6c42\u6839\u516c\u5f0f\u53ef\u5f97 \\(\\displaystyle x=\\frac{{\\sqrt 5 c \\; \\pm \\sqrt \\Delta\u00a0 }}{2}\\)<\/span> \u3002<\/p>\n
\u516c\u5f0f\u4e2d\u5176\u4e2d\u6d89\u53ca\u5230 \\(\\sqrt \\Delta\\) \u7684\u90e8\u5206\uff0c\u53ef\u4ee5\u91c7\u7528 Cipolla \u6c42\u89e3\u3002<\/p>\n
\u5176\u4e2d \\(\\left(-1\\right)^n\\) \u53ef\u4ee5\u6839\u636e \\(n\\) \u7684\u5947\u5076\u6027\u5206\u6210 \\(-1\\) \u548c \\(1\\) \u4e24\u79cd\u53d6\u503c\uff0c\u5206\u7c7b\u8ba8\u8bba\u3002<\/p>\n
\u53c8\u56e0\u4e3a \\(t^n = x\\) \uff0c\u6240\u4ee5\u8dd1 BSGS \u6c42\u51fa \\(n\\) \u7684\u6700\u5c0f\u6b63\u6574\u6570\u89e3\uff0c\u5e76\u4e0e\u5176\u4ed6\u60c5\u51b5\u6c42\u51fa\u7684 \\(n\\) \u53d6\u6700\u5c0f\u5373\u53ef\u5f97\u51fa\u7b54\u6848\u3002<\/p>\n
<\/p>\n
- \n
- \n
Section C<\/h3>\n<\/li>\n<\/ul>\n
\u4f1a BSGS \u7684\u4eba\u53ef\u4ee5\u53bb AC \u4e86\u3002<\/p>\n
BSGS (Baby-step giant-step)<\/a> \u662f\u6c42\u89e3\u6a21\u610f\u4e49\u4e0b\u65b9\u7a0b \\(\\displaystyle {a^x} \\equiv b\\pmod p\\) \uff08\u8fd9\u91cc\u5047\u8bbe \\(p\\) \u4e3a\u8d28\u6570\uff09\u4e2d \\(x\\) \u7684\u6700\u5c0f\u6b63\u6574\u6570\u89e3\u7684\u4e00\u79cd\u65b9\u6cd5\u3002<\/p>\n
\u9996\u5148\uff0c\u6700\u5c0f\u6b63\u6574\u6570\u89e3 \\(x\\) \u4e0d\u4f1a\u8d85\u8fc7 \\(p-1\\) \u3002<\/p>\n
\u82e5 \\(x \\geq p\\) \uff0c\u90a3\u4e48\u53ef\u4ee5\u8bbe \\(\\displaystyle x=i\\left(p-1\\right)+j\\) \uff0c\u5176\u4e2d \\(i \\geq 1, 0 \\leq j < p-1\\) \u3002<\/p>\n
\u90a3\u4e48\u6709 \\(\\displaystyle {a^x} = {a^{i\\left(p-1\\right) + j}} = {a^{i\\left(p-1\\right)}}{a^j} \\equiv b\\pmod p\\) \u3002<\/p>\n
\u56e0\u4e3a \\(p\\) \u4e3a\u8d28\u6570\uff0c\\(a < p\\) \uff0c\u6240\u4ee5\u7531\u8d39\u9a6c\u5c0f\u5b9a\u7406\u5f97 \\(\\displaystyle a^{p-1} \\equiv 1\\pmod p\\) \u3002<\/p>\n
\u6240\u4ee5\u6709 \\(\\displaystyle {a^x} = {a^{ip}}{a^j} \\equiv {a^j} \\equiv b\\pmod p\\) \uff0c\u5373 \\(\\displaystyle a^x \\equiv a^{x \\bmod \\left(p-1\\right)} \\pmod p\\) \u3002<\/p>\n
\u6240\u4ee5\u53ea\u9700\u8981\u5728 \\((0, p-1]\\) \u5185\u5bfb\u627e \\(x\\) \u5373\u53ef\u3002<\/p>\n
\u66b4\u529b\u679a\u4e3e\u4e0d\u73b0\u5b9e\uff0c\u5c1d\u8bd5\u5c06 \\(p\\) \u5206\u6210\u4e24\u90e8\u5206\uff0c\u5373\u8bbe \\(\\displaystyle s=\\lceil \\sqrt p \\rceil\\)\uff0c\u90a3\u4e48 \\(x\\) \u53ef\u4ee5\u5206\u89e3\u4e3a \\(is-j\\) \uff0c\u5176\u4e2d \\(0 < i \\leq s, 0 \\leq j < s\\) \u3002<\/p>\n
\u90a3\u4e48\u6709 \\(\\displaystyle {a^x} = {a^{is – j}} \\equiv b\\pmod p\\) \uff0c\u5373 \\(\\displaystyle {a^{is}} \\equiv b{a^j}\\pmod p\\) \u3002<\/p>\n
\u679a\u4e3e \\(j\\) \uff0c\u628a\u7b49\u53f7\u53f3\u8fb9\u7684\u503c\u5b58\u5230 hash_table\uff08\\(O(1)\\)\uff09 \u6216 std::map \uff08\\(O(\\log s)\\)\uff09\u4e2d\uff0c\u7136\u540e\u679a\u4e3e \\(i\\) \u914d\u5bf9\u3002<\/p>\n
\u56e0\u4e3a \\(i, j\\) \u6700\u591a\u53ea\u5230 \\(\\displaystyle s=\\lceil \\sqrt p \\rceil\\) \uff0c\u6240\u4ee5\u590d\u6742\u5ea6\u4e3a\u00a0\\(O(\\sqrt p)\\) \u6216 \\(O(\\sqrt p \\log p)\\)\u3002<\/p>\n
<\/p>\n
- \n
- \n
Section D<\/h3>\n<\/li>\n<\/ul>\n
\u4f1a Cipolla \u7684\u4eba\u53ef\u4ee5\u53bb AC \u4e86\u3002<\/p>\n
Cipolla<\/a> \u662f\u4e00\u79cd\u6c42\u89e3\u4e8c\u6b21\u5269\u4f59\u7684\u9ad8\u6548\u7b97\u6cd5\u3002<\/p>\n
\u867d\u7136\u6c42\u89e3\u4e8c\u6b21\u5269\u4f59\u4e5f\u53ef\u4ee5\u4f7f\u7528 BSGS\uff0c\u4f46\u662f\u4f7f\u7528 Cipolla \u65f6\u95f4\u590d\u6742\u5ea6\u4f1a\u6bd4\u4e4b\u4f18\u79c0
\uff08\u4e5f\u4e0d\u77e5\u9053\u6211\u80fd\u4e0d\u80fd\u6210\u529f\u5361\u6389\uff09<\/s>\u3002<\/p>\n\u5bf9\u4e8e\u5947\u8d28\u6570 \\(p\\) \u53ca\u6574\u6570 \\(n\\)\uff0c\u82e5\u5b58\u5728\u6574\u6570 \\(x, 0 \\leq x < p\\) \u4e14\u6ee1\u8db3 \\(\\displaystyle x^2 \\equiv n\\pmod p\\) \uff0c\u90a3\u4e48 \\(n\\) \u5c31\u79f0\u4f5c\u5728\u6a21 \\(p\\) \u610f\u4e49\u4e0b\u7684\u4e8c\u6b21\u5269\u4f59\u3002<\/p>\n
\u5b9a\u4e49\u6570\u57df \\(\\displaystyle \\mathbb {F}_p\\) \u5305\u542b \\([0, p-1]\\) \u4e2d\u7684\u6574\u6570\uff0c\u5176\u4e2d\u7684\u8fd0\u7b97\u5747\u5728\u6a21\u610f\u4e49\u4e0b\u8fdb\u884c\u3002\u82e5\u65e0\u7279\u6b8a\u8bf4\u660e\uff0c\u4e0b\u5217\u64cd\u4f5c\u5747\u5728 \\(\\displaystyle \\mathbb {F}_p\\) \u4e0b\u8fdb\u884c\u3002<\/p>\n
\u5148\u6765\u8bc1\u660e\u51e0\u4e2a\u5f15\u7406\u3002<\/p>\n
\\(Lemma.1\\)<\/span>\uff1a\u5bf9\u4e8e\u65b9\u7a0b \\(\\displaystyle x^2 \\equiv n \\pmod p\\) \uff0c\u603b\u5171\u53ea\u6709 \\(\\displaystyle \\frac{p-1}{2}\\) \u4e2a \\(n\\)\uff08\\(0<n<p\\)\uff09 \u4f7f\u5f97 \\(x\\) \u6709\u89e3\u3002<\/p>\n
\\(Proof\\)<\/span>\uff1a\u5047\u8bbe\u5b58\u5728\u4e24\u4e2a\u4e0d\u540c\u7684\u6570 \\(u, v\\) \u4f7f\u5f97 \\(\\displaystyle u^2 \\equiv v^2 \\pmod p\\) \uff0c\u90a3\u4e48\u6709 \\(\\displaystyle p\\; |\\; \\left(u^2-v^2\\right)\\) \uff0c\u5373 \\(\\displaystyle p\\; |\\; \\left(u+v\\right)\\left(u-v\\right)\\) \u3002<\/p>\n
\u7531\u4e8e \\(\\displaystyle p\\; \\not |\\; \\left(u-v\\right)\\)\uff0c\u6240\u4ee5\u00a0\\(\\displaystyle p\\; |\\; \\left(u+v\\right)\\) \uff0c\u5373 \\(\\displaystyle u+v \\equiv 0 \\pmod p\\) \u3002<\/p>\n
\u6240\u4ee5 \\((0,p-1]\\) \u4e2d \\(\\displaystyle x^2 \\equiv \\left(p-x\\right)^2 \\pmod p\\)\uff0c\u6709\u4e14\u53ea\u6709 \\(\\displaystyle \\frac{p-1}{2}\\) \u5bf9\u8fd9\u6837\u7684\u6570\uff0c\u6240\u4ee5\u6709\u4e14\u53ea\u6709 \\(\\displaystyle \\frac{p-1}{2}\\) \u79cd\u4e0d\u540c\u7684 \\(n\\)\uff0c\u5f97\u8bc1\u3002<\/p>\n
\\(Lemma.2\\)<\/span>\uff1a\u5b9a\u4e49 \u52d2\u8ba9\u5fb7\u7b26\u53f7 (Legendre symbol)<\/a> \\(\\displaystyle \\left(\\frac{a}{p}\\right)=\\begin{cases}1,&a\\text{\u5728\u6a21$p$\u610f\u4e49\u4e0b\u662f\u4e8c\u6b21\u5269\u4f59}\\\\-1,&a\\text{\u5728\u6a21$p$\u610f\u4e49\u4e0b\u662f\u975e\u4e8c\u6b21\u5269\u4f59}\\\\0,&a\\equiv0\\pmod p\\end{cases}\\)<\/p>\n
\u7136\u540e\u6709 \\(\\displaystyle \\left(\\frac{a}{p}\\right)\\equiv a^{\\frac{p-1}{2}}\\pmod p\\)<\/span> \uff08\u5373 \u6b27\u62c9\u5224\u522b\u6cd5 (Euler’s criterion)<\/a>\uff09\u3002<\/p>\n
\\(Proof\\)<\/span>\uff1a\u5f53 \\(a\\) \u5728\u6a21 \\(p\\) \u610f\u4e49\u4e0b\u662f\u4e8c\u6b21\u5269\u4f59\uff0c\u5373 \\(\\displaystyle \\left(\\frac{a}{p}\\right)\\equiv a^{\\frac{p-1}{2}} \\equiv 1\\pmod p\\)<\/span> \u65f6\uff1a\u8bbe \\(\\displaystyle x^2 \\equiv a\\pmod p\\) \uff0c\u6240\u4ee5\u6709 \\(\\displaystyle x^{p-1} \\equiv a^{\\frac{p-1}{2}} \\equiv 1\\pmod p\\) <\/span>\u3002<\/p>\n
\u6839\u636e\u8d39\u9a6c\u5c0f\u5b9a\u7406\u53ef\u77e5\u8fd9\u6837\u7684 \\(x\\) \u5b58\u5728\uff0c\u6545\u539f\u547d\u9898\u5f97\u8bc1\u3002<\/p>\n
\u5f53 \\(a\\) \u5728\u6a21 \\(p\\) \u610f\u4e49\u4e0b\u4e0d\u662f\u4e8c\u6b21\u5269\u4f59\uff0c\u5373 \\(\\displaystyle \\left(\\frac{a}{p}\\right)\\equiv a^{\\frac{p-1}{2}} \\equiv -1\\pmod p\\)<\/span> \u65f6\uff1a\u8bbe \\(\\displaystyle x^2 \\equiv a\\pmod p\\) \uff0c\u6240\u4ee5\u6709 \\(\\displaystyle x^{p-1} \\equiv a^{\\frac{p-1}{2}} \\equiv -1\\pmod p\\) <\/span>\u3002<\/p>\n
\u6839\u636e\u8d39\u9a6c\u5c0f\u5b9a\u7406\u53ef\u77e5\u8fd9\u6837\u7684 \\(x\\) \u4e0d\u5b58\u5728\uff0c\u6545\u539f\u547d\u9898\u5f97\u8bc1\u3002<\/p>\n
\u5f53 \\(\\displaystyle \\left(\\frac{a}{p}\\right)\\equiv a^{\\frac{p-1}{2}} \\equiv 0\\pmod p\\)<\/span> \u65f6\uff1a\u663e\u7136\u3002<\/p>\n
\u7531\u4e8e\u8fd9\u4e2a\u7b97\u6cd5\u6784\u9020\u5de7\u5999\uff0c\u6240\u4ee5\u5148\u4ecb\u7ecd\u5176\u5b9e\u73b0\u65b9\u6cd5\u3002<\/p>\n
1\uff0c\u7ed9\u5b9a \\(n\\) \uff0c\u82e5 \\(\\displaystyle \\left(\\frac{n}{p}\\right) \\neq 1\\) \uff0c\u5219\u53ef\u4ee5\u76f4\u63a5\u7ed9\u51fa\u7b54\u6848\u3002<\/p>\n
2\uff0c\u968f\u673a \\(a\\) \u76f4\u5230 \\(\\displaystyle \\left(\\frac{a^2-n}{p}\\right) = -1\\) \u3002\u7531 \u5f15\u74061 \u53ef\u77e5\uff0c\u671f\u671b\u968f\u673a\u6b21\u6570\u4e3a \\(2\\)\u3002<\/p>\n
3\uff0c\u6269\u5c55\u81f3 \\(\\displaystyle \\mathbb{F}_{p^2}\\)\uff0c\u5e76\u628a \\(\\displaystyle \\sqrt{a^2-n}\\) \u4f5c\u4e3a\u201c\u7b2c\u4e8c\u6761\u6570\u8f74\u201d\u7684\u5355\u4f4d\u957f\u5ea6\uff08\u53ef\u7c7b\u6bd4\u590d\u6570\uff09\u3002\u8fd9\u6837\uff0c\u6b64\u57df\u4e2d\u7684\u6570\u53ef\u4ee5\u8868\u793a\u4e3a \\(\\displaystyle a+b\\omega\\) \uff0c\u5176\u4e2d \\(\\displaystyle \\omega^2 = a^2-n\\) \uff0c\u5e76\u4e14\u6b64\u6570\u57df\u4f9d\u7136\u6ee1\u8db3\u4ea4\u6362\u5f8b\u3001\u7ed3\u5408\u5f8b\u4ee5\u53ca\u5206\u914d\u5f8b\u3002<\/p>\n
Q\uff1a\u4e3a\u4ec0\u4e48\u8d34\u56fe\uff1f\u00a0\u00a0 A\uff1a\u56e0\u4e3a\u6211\u770b\u4e0d\u61c2<\/s><\/span><\/p>\n![\"\"](\"https:\/\/cf.mnihyc.com\/blog\/wp-content\/uploads\/2019\/08\/2019-08-03_2333221.png\")
<\/p>\n<\/p>\n
4\uff0c\u5c06 \\(x\\) \u4e5f\u6269\u5c55\u81f3 \\(\\displaystyle \\mathbb{F}_{p^2}\\)\uff0c\\(\\displaystyle x \\equiv \\left(a+\\omega\\right)^{\\frac{p+1}{2}} \\pmod p \\)<\/span> \uff0c\u53d6 \\(x\\)\u201c\u7b2c\u4e00\u6761\u6570\u8f74\u201d\u4e2d\u7684\u90e8\u5206\u5373\u4e3a\u7b54\u6848\u3002<\/p>\n
\u8981\u8bc1\u660e\u6216\u8005\u641e\u61c2\u8fd9\u4e2a\u662f\u5728\u8bf4\u4ec0\u4e48\uff0c\u8fd8\u9700\u8981\u518d\u8bc1\u660e\u4e00\u4e9b\u5f15\u7406\u3002<\/p>\n
\\(Lemma.3\\)<\/span>\uff1a\\(\\displaystyle \\omega^p \\equiv – \\omega \\pmod p\\)<\/span><\/p>\n
\\(Proof\\)<\/span>\uff1a\\(\\displaystyle {\\omega ^p} \\equiv \\omega\u00a0 \\cdot {\\omega ^{p – 1}} \\equiv \\omega {\\left( {{\\omega ^2}} \\right)^{\\frac{{p – 1}}{2}}} \\equiv \\omega {\\left( {{a^2} – n} \\right)^{\\frac{{p – 1}}{2}}} \\equiv\u00a0 – \\omega \\pmod p\\)<\/span><\/p>\n
\\(Lemma.4\\)<\/span>\uff1a\\(\\displaystyle \\left(a+b\\right)^p \\equiv a^p+b^p \\pmod p\\)<\/span><\/p>\n
\\(Proof\\)<\/span>\uff1a\u6839\u636e\u4e8c\u9879\u5f0f\u5b9a\u7406\u5c55\u5f00\uff0c\u6709 \\(\\displaystyle \\left(a+b\\right)^p \\equiv \\sum\\limits_{i=0}^pC_p^ia^ib^{p-i} \\pmod p\\)<\/span> \uff0c\u7531\u4e8e\u5f53 \\(0<i<p\\) \u65f6 \\(\\displaystyle C_p^i \\equiv 0 \\pmod p\\)\uff0c\u6240\u4ee5\u5f97\u8bc1\u3002<\/p>\n
\u73b0\u5728\u5df2\u7ecf\u53ef\u4ee5\u6765\u8bc1\u660e\u300c\u6b65\u9aa44\u300d\u4e86\u3002<\/p>\n
\u6839\u636e\u53d9\u8ff0\uff0c\u5df2\u77e5 \\(\\displaystyle x \\equiv \\left(a+\\omega\\right)^{\\frac{p+1}{2}} \\pmod p\\)<\/span>\uff0c\u5373\u00a0\\(\\displaystyle x^2 \\equiv \\left(a+\\omega\\right)^{p+1} \\pmod p\\) \u3002<\/p>\n
\u6839\u636e \u5f15\u74064 \uff0c\u6709 \\(\\displaystyle \\left(a+\\omega\\right)^{p+1} \\equiv \\left(a+\\omega\\right)\\left(a+\\omega\\right)^p \\equiv \\left(a+\\omega\\right)\\left(a^p+\\omega^p\\right) \\pmod p\\) \u3002<\/p>\n
\u6839\u636e\u8d39\u9a6c\u5c0f\u5b9a\u7406 \\(\\displaystyle a^p \\equiv a \\pmod p\\) \u4ee5\u53ca \u5f15\u74063\uff0c\u53ef\u5f97 \\(\\displaystyle \\left(a+\\omega\\right)\\left(a^p+\\omega^p\\right) \\equiv \\left(a+\\omega\\right)\\left(a-\\omega\\right) \\pmod p\\) \u3002<\/p>\n
\u6240\u4ee5\u6709 \\(\\displaystyle x^2 \\equiv \\left(a+\\omega\\right)\\left(a-\\omega\\right) \\equiv a^2-\\omega^2 \\equiv a^2-\\left(a^2-n\\right) \\equiv n \\pmod p\\) \uff0c\u53ef\u8bc1 \\(x\\) \u4e3a\u6b64\u65b9\u7a0b\u7684\u4e00\u4e2a\u5408\u6cd5\u89e3\u3002<\/p>\n
\u7b49\u7b49\uff0c\u521a\u521a\u300c\u6b65\u9aa44\u300d\u91cc\u4e0d\u662f\u8bf4\u300c\u53d6 \\(x\\)\u201c\u7b2c\u4e00\u6761\u6570\u8f74\u201d\u4e2d\u7684\u90e8\u5206\u5373\u4e3a\u7b54\u6848\u300d\u5417\uff1f\u4e0a\u9762\u7684\u8bc1\u660e\u90fd\u662f\u5728 \\(\\displaystyle \\mathbb{F}_{p^2}\\) \u4e2d\u8fdb\u884c\u7684\uff0c\u600e\u4e48\u80fd\u76f4\u63a5\u53d6\u5176\u4e2d\u7684\u4e00\u90e8\u5206\uff08\u4fdd\u8bc1\u89e3\u53ef\u4ee5\u88ab\u538b\u7f29\u5230 \\(\\displaystyle \\mathbb{F}_{p}\\)\uff09\uff1f<\/p>\n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n