{"id":3404,"date":"2019-03-30T22:18:08","date_gmt":"2019-03-30T17:48:08","guid":{"rendered":"https:\/\/quera.ir\/blog\/?p=3404"},"modified":"2022-01-06T07:08:39","modified_gmt":"2022-01-06T07:08:39","slug":"%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c","status":"publish","type":"post","link":"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/","title":{"rendered":"\u067e\u0627\u0633\u062e \u0633\u0648\u0627\u0644\u0627\u062a \u0645\u0633\u0627\u0628\u0642\u0647 \u06f2\u06f6 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u06cc"},"content":{"rendered":"\n

\u062e\u0628 \u0628\u062f\u0648\u0646 \u0645\u0642\u062f\u0645\u0647 \u0645\u06cc\u0631\u06cc\u0645 \u0633\u0631\u0627\u063a \u0633\u0648\u0627\u0644 \u0647\u0627 :<\/p>\n\n\n\n

\u0633\u0648\u0627\u0644 \u0646\u0641\u0633\u200c\u06af\u06cc\u0631:\u200c<\/a><\/p>\n\n\n\n

\u0628\u0631\u0627\u06cc \u0633\u0648\u0627\u0644 <\/span> \u0627\u0645 \u060c a_i \\times b_i <\/span> \u0628\u0627\u0631 \u0646\u0641\u0633 \u0647\u0627 \u06af\u0631\u0641\u062a\u0647 \u0645\u06cc \u0634\u0648\u062f. \u067e\u0633 \u067e\u0627\u0633\u062e \u0628\u0631\u0627\u0628\u0631 \u0627\u0633\u062a \u0628\u0627 \\sum_{i=1}^{n} a_i \\times b_i <\/span>.<\/p>\n\n\n\n\n\n\n\n

\u06a9\u062f ++C<\/a> \u0627\u0632 \u0633\u0627\u06cc\u06cc\u0646 \u0627\u0639\u0644\u0627<\/a><\/p>\n\n\n\n

\u06a9\u062f Python 3<\/a> \u0627\u0632 \u0639\u0644\u06cc \u06a9\u0627\u0648\u06cc\u0627\u0646\u06cc<\/a><\/p>\n\n\n\n

\u06a9\u062f Java<\/a> \u0627\u0632 \u0645\u0639\u0635\u0648\u0645\u0647 \u0627\u0628\u0631\u0627\u0647\u06cc\u0645\u06cc<\/a><\/p>\n\n\n\n

\u06a9\u062f Mono C#<\/a> \u0627\u0632 \u0645\u062d\u0645\u062f \u0627\u062d\u0633\u0627\u0646 \u0634\u0639\u0628\u0627\u0646\u06cc<\/a><\/p>\n\n\n\n

\u0645\u0633\u0626\u0644\u0647 \u0647\u0627\u0644\u062a:<\/a><\/p>\n\n\n\n

\u0628\u0631\u0646\u0627\u0645\u0647 \u0631\u0627 \u0634\u0628\u06cc\u0647 \u0633\u0627\u0632\u06cc \u0645\u06cc \u06a9\u0646\u06cc\u0645 \u0648 \u062e\u0637 \u0628\u0647 \u062e\u0637 \u0622\u0646 \u0631\u0627 \u0627\u062c\u0631\u0627 \u0645\u06cc \u06a9\u0646\u06cc\u0645. \u0686\u0648\u0646 \u0648\u0631\u0648\u062f\u06cc \u0647\u0627\u06cc \u062f\u0633\u062a\u0648\u0631 goto \u062b\u0627\u0628\u062a \u0647\u0633\u062a\u0646\u062f \u0627\u06af\u0631 \u06cc\u06a9 \u062f\u0633\u062a\u0648\u0631 \u0631\u0627 \u062f\u0648 \u0628\u0627\u0631 \u0628\u0628\u06cc\u0646\u06cc\u0645 \u0647\u06cc\u0686 \u0648\u0642\u062a \u0628\u0631\u0646\u0627\u0645\u0647 \u062a\u0645\u0627\u0645 \u0646\u0645\u06cc \u0634\u0648\u062f. \u067e\u0633 \u0647\u0631 \u062e\u0637\u06cc \u06a9\u0647 \u0645\u06cc\u0628\u06cc\u0646\u06cc\u0645 \u0631\u0627 \u0645\u0627\u0631\u06a9 \u0645\u06cc \u06a9\u0646\u06cc\u0645 \u0648 \u0627\u06af\u0631 \u0628\u0647 \u062e\u0637 \u0645\u0627\u0631\u06a9 \u0634\u062f\u0647 \u0627\u06cc \u062f\u0648\u0628\u0627\u0631\u0647 \u0631\u0633\u06cc\u062f\u06cc\u0645 \u060c -1<\/span> \u0686\u0627\u067e \u0645\u06cc \u06a9\u0646\u06cc\u0645. \u0627\u06af\u0631 \u0647\u0645 \u06a9\u0647 \u0628\u0631\u0646\u0627\u0645\u0647 \u062a\u0645\u0627\u0645 \u0634\u062f \u0645\u0642\u0627\u062f\u06cc\u0631 cout \u0631\u0627 \u062f\u0631 \u0627\u0646\u062a\u0647\u0627 \u0686\u0627\u067e \u0645\u06cc \u06a9\u0646\u06cc\u0645.<\/p>\n\n\n\n

\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc O(n) <\/span><\/p>\n\n\n\n

\u062e\u0633\u062a\u06af\u0627\u0646:<\/a><\/p>\n\n\n\n

\u0627\u0645\u06cc\u062f \u0631\u06cc\u0627\u0636\u06cc \u062a\u0639\u062f\u0627\u062f \u0627\u0639\u062f\u0627\u062f \u0645\u062a\u0641\u0627\u0648\u062a \u0628\u0631\u0627\u0628\u0631 \u0627\u0633\u062a \u0628\u0627 \u062c\u0645\u0639 \u0627\u062d\u062a\u0645\u0627\u0644 \u0627\u06cc\u0646 \u06a9\u0647 \u0639\u062f\u062f x<\/span> \u0631\u0648\u06cc \u0633\u0631\u062f\u0631 \u0634\u0627\u0632 \u0646\u0635\u0628 \u0634\u0648\u062f \u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0645\u0647 x<\/span> \u0647\u0627\u06cc \u0645\u0645\u06a9\u0646. \u0627\u0632 O(n^2) <\/span> \u0645\u06cc \u062a\u0648\u0627\u0646\u06cc\u0645 x<\/span> \u0647\u0627\u06cc\u06cc \u06a9\u0647 \u0627\u062d\u062a\u0645\u0627\u0644\u0634\u0627\u0646 0<\/span> \u0646\u06cc\u0633\u062a(\u062c\u0645\u0639 \u062d\u062f\u0627\u0642\u0644 \u06cc\u06a9 \u0628\u0627\u0632\u0647 \u0647\u0633\u062a\u0646\u062f) \u0631\u0627 \u0628\u062f\u0633\u062a \u0622\u0648\u0631\u06cc\u0645. \u062d\u0627\u0644 \u0628\u0647 \u0627\u0632\u0627\u06cc \u06cc\u06a9 \u0639\u062f\u062f x<\/span> \u0645\u06cc \u062e\u0648\u0627\u0647\u06cc\u0645 \u0627\u062d\u062a\u0645\u0627\u0644 \u0627\u06cc\u0646 \u06a9\u0647 x<\/span> \u0648\u062c\u0648\u062f \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u062f \u0631\u0627 \u0628\u062f\u0633\u062a \u0622\u0648\u0631\u06cc\u0645. dp_a <\/span> \u0631\u0627 \u0628\u0631\u0627\u0628\u0631 \u062a\u0639\u062f\u0627\u062f \u062d\u0627\u0644\u062a \u0633\u0627\u062e\u062a\u0647 \u0646\u0634\u062f\u0646 x<\/span> \u062f\u0631 a<\/span> \u062a\u0627\u06cc \u0627\u0648\u0644 \u062f\u0646\u0628\u0627\u0644\u0647 \u062f\u0631 \u0646\u0638\u0631 \u0645\u06cc \u06af\u06cc\u0631\u06cc\u0645. dp_a = \\sum_{b=0}^{a-1} dp_b <\/span> \u0628\u0647 \u0634\u0631\u0637\u06cc \u06a9\u0647 \u062c\u0645\u0639 \u0628\u0627\u0632\u0647 (b,a]<\/span> \u0628\u0631\u0627\u0628\u0631 x<\/span> \u0646\u0628\u0627\u0634\u062f.\u067e\u0633 \u0627\u06af\u0631 \u0628\u0647 \u0627\u0632\u0627\u06cc x<\/span> \u062a\u0639\u062f\u0627\u062f \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc\u06cc \u06a9\u0647 \u062c\u0645\u0639\u0634\u0627\u0646 x<\/span> \u0627\u0633\u062a \u0631\u0627 cnt<\/span> \u0628\u0646\u0627\u0645\u06cc\u0645 \u0622\u0646\u06af\u0627\u0647 \u0645\u06cc \u062a\u0648\u0627\u0646 dp<\/span> \u0631\u0627 \u0627\u0632 O(n+cnt)<\/span> \u0645\u06cc \u062a\u0648\u0627\u0646 \u0645\u062d\u0627\u0633\u0628\u0647 \u06a9\u0631\u062f.\u0627\u062d\u062a\u0645\u0627\u0644 \u062d\u0636\u0648\u0631 x<\/span> \u0647\u0645 \u0645\u06cc \u0634\u0648\u062f - \\frac{dp_n}{2^{n-1}} <\/span> 1 . \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc O(n^3) <\/span><\/p>\n\n\n\n

\u0627\u0631\u062a\u0628\u0627\u0637\u0627\u062a \u0641\u0627\u0645\u06cc\u0644\u06cc:<\/a><\/p>\n\n\n\n

\u0627\u0628\u062a\u062f\u0627 \u062d\u0644\u06cc \u0628\u0627 O(n^2)<\/span> \u0631\u0627 \u0628\u0631\u0631\u0633\u06cc \u0645\u06cc \u06a9\u0646\u06cc\u0645.\u0628\u0627\u06cc\u062f \u06af\u0631\u0627\u0641\u06cc \u0628\u0633\u0627\u0632\u06cc\u0645 \u06a9\u0647 \u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0631\u0627\u0628\u0637\u0647 \u0645\u062b\u0644 \u0639\u0645\u0648 \u0627\u06af\u0631 b<\/span> \u0639\u0645\u0648\u06cc a<\/span> \u0628\u0648\u062f \u0622\u0646\u06af\u0627\u0647 \u0627\u0632 a<\/span> \u0628\u0647 b<\/span> \u06cc\u0627\u0644\u06cc \u062c\u0647\u062a \u062f\u0627\u0631 \u0642\u0631\u0627\u0631 \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u062f \u06a9\u0647 \u0631\u0648\u06cc \u0622\u0646 \u0648\u0627\u0698\u0647 \u0639\u0645\u0648 \u0646\u0648\u0634\u062a\u0647 \u0634\u062f\u0647 \u0627\u0633\u062a. \u062d\u0627\u0644\u0627 \u062c\u0647\u062a \u06cc\u0627\u0644 \u0647\u0627\u06cc \u06af\u0631\u0627\u0641 \u0631\u0627 \u0628\u0631\u0639\u06a9\u0633 \u0645\u06cc \u06a9\u0646\u06cc\u0645.\u06a9\u0648\u062a\u0627\u0647 \u062a\u0631\u06cc\u0646 \u0645\u0633\u06cc\u0631 \u0627\u0632 b<\/span> \u0628\u0647 a<\/span> \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u062f(\u0648 \u062f\u0631 \u0635\u0648\u0631\u062a\u06cc\u06a9\u0647 \u0686\u0646\u062f \u06a9\u0648\u062a\u0627\u0647 \u062a\u0631\u06cc\u0646 \u0645\u0633\u06cc\u0631 \u0628\u0648\u062f \u0645\u0633\u06cc\u0631\u06cc \u06a9\u0647 \u0627\u0632 \u0644\u062d\u0627\u0638 \u0644\u063a\u062a \u0646\u0627\u0645\u0647 \u0627\u06cc \u0645\u0627\u06a9\u0633\u06cc\u0645\u0645 \u0627\u0633\u062a \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u062f).\u062c\u0648\u0627\u0628 \u0645\u0633\u0626\u0644\u0647 \u0631\u0634\u062a\u0647 \u0645\u062a\u0646\u0627\u0638\u0631 \u0628\u0627 \u0627\u06cc\u0646 \u0645\u0633\u06cc\u0631 \u0627\u0633\u062a!(\u062f\u0631 \u0627\u0646\u062a\u0647\u0627 \u062a\u0648\u0636\u06cc\u062d \u0645\u06cc \u062f\u0647\u06cc\u0645 \u06a9\u0647 \u0686\u0637\u0648\u0631 \u0645\u06cc \u062a\u0648\u0627\u0646 \u06cc\u06a9 \u06a9\u0648\u062a\u0627\u0647 \u062a\u0631\u06cc\u0646 \u0645\u0633\u06cc\u0631 \u0628\u0627 \u0634\u0631\u0637 \u0628\u0632\u0631\u06af\u062a\u0631\u06cc\u0646 \u0628\u0648\u062f\u0646 \u0627\u0632 \u0644\u062d\u0627\u0638 \u062a\u0631\u062a\u06cc\u0628 \u0644\u063a\u062a \u0646\u0627\u0645\u0647 \u0627\u06cc \u0631\u0627 \u06cc\u0627\u0641\u062a).<\/p>\n\n\n\n

\u062d\u0627\u0644\u0627 \u0628\u0631\u0627\u06cc \u0627\u06cc\u0646\u06a9\u0647 \u062a\u0639\u062f\u0627\u062f \u06cc\u0627\u0644 \u0647\u0627\u06cc \u06af\u0631\u0627\u0641 \u0631\u0627 \u06a9\u0645 \u06a9\u0646\u06cc\u0645 \u0627\u0632 \u0627\u06cc\u062f\u0647 \u0627\u0636\u0627\u0641\u0647 \u06a9\u0631\u062f\u0646 \u0631\u0627\u0633 \u0627\u0633\u062a\u0641\u0627\u062f\u0647 \u0645\u06cc \u06a9\u0646\u06cc\u0645. \u0628\u0647 \u0627\u06cc\u0646 \u0635\u0648\u0631\u062a \u06a9\u0647 \u0627\u06af\u0631 \u0628\u062e\u0648\u0627\u0647\u06cc\u0645 \u0645\u062c\u0645\u0648\u0639\u0647 \u0631\u0627\u0633 \u0647\u0627\u06cc A<\/span> \u0631\u0627 \u0628\u0647 \u0645\u062c\u0645\u0648\u0639\u0647 \u0631\u0627\u0633 \u0647\u0627\u06cc B<\/span> \u0648\u0635\u0644 \u06a9\u0646\u06cc\u0645 \u0648 \u0631\u0648\u06cc \u0647\u0645\u0647 \u06cc\u0627\u0644 \u0647\u0627 \u0631\u0634\u062a\u0647 s<\/span> \u0631\u0627 \u0628\u0646\u0648\u06cc\u0633\u06cc\u0645 \u0622\u0646\u06af\u0627\u0647 \u0628\u0647 \u062c\u0627\u06cc \u0627\u06cc\u0646\u06a9\u0627\u0631 \u06cc\u06a9 \u0631\u0627\u0633 \u062c\u062f\u06cc\u062f \u0627\u0636\u0627\u0641\u0647 \u06a9\u0631\u062f\u0647 \u0648 \u0647\u0645\u0647 A<\/span> \u0631\u0627 \u0628\u0647 \u0631\u0627\u0633 \u062c\u062f\u06cc\u062f \u0648 \u0631\u0627\u0633 \u062c\u062f\u06cc\u062f \u0631\u0627 \u0628\u0647 \u0647\u0645\u0647 \u200cB<\/span> \u0648\u0635\u0644 \u0645\u06cc\u06a9\u0646\u06cc\u0645 \u0648 \u0631\u0648\u06cc \u0631\u0627\u0633 \u062c\u062f\u06cc\u062f \u0631\u0634\u062a\u0647 s<\/span> \u0631\u0627 \u0645\u06cc \u0646\u0648\u06cc\u0633\u06cc\u0645(\u0627\u06cc\u0646 \u0639\u0645\u0644\u06cc\u0627\u062a f_{A,B,s}<\/span> \u0646\u0627\u0645\u06af\u0630\u0627\u0631\u06cc \u0645\u06cc \u06a9\u0646\u06cc\u0645) . \u062a\u0648\u062c\u0647 \u06a9\u0646\u06cc\u062f \u06a9\u0647 \u062f\u0631 \u0627\u06cc\u0646 \u06af\u0631\u0627\u0641 \u062c\u062f\u06cc\u062f \u0631\u0634\u062a\u0647 \u0647\u0627 \u0631\u0648\u06cc \u0631\u0627\u0633 \u0647\u0627 \u0646\u0648\u0634\u062a\u0647 \u0645\u06cc \u0634\u0648\u0646\u062f \u0646\u0647 \u06cc\u0627\u0644 \u0647\u0627!<\/p>\n\n\n\n

\u0628\u0631\u0627\u06cc \u0633\u0627\u062e\u062a\u0646 \u0631\u0627\u0628\u0637\u0647 \u0647\u0627\u06cc \u067e\u062f\u0631 \u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0631\u0627\u0633 \u0645\u062b\u0644 u<\/span> \u0628\u0627\u06cc\u062f f_{A,B,pedar}<\/span> \u0631\u0627 \u0627\u062c\u0631\u0627 \u06a9\u0646\u06cc\u0645:<\/p>\n\n\nA={u}<\/span>\n\n\n\nB={par1_u,par2_u}<\/span>\n\n\n\n

\u0633\u0627\u062e\u062a\u0646 \u0631\u0627\u0628\u0637\u0647 \u0647\u0627\u06cc \u067e\u0633\u0631 \u0645\u0634\u0627\u0628\u0647 \u067e\u062f\u0631 \u0627\u0646\u062c\u0627\u0645 \u0645\u06cc \u0634\u0648\u062f.<\/p>\n\n\n\n

\u0628\u0631\u0627\u06cc \u0633\u0627\u062e\u062a\u0646 \u0631\u0627\u0628\u0637\u0647 \u0647\u0627\u06cc \u0628\u0631\u0627\u062f\u0631 \u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0631\u0627\u0633 \u0645\u062b\u0644 u<\/span> \u0628\u0627\u06cc\u062f f_{A,B,baradar}<\/span> \u0631\u0627 \u0627\u062c\u0631\u0627 \u06a9\u0646\u06cc\u0645:<\/p>\n\n\nA=B=sons_u<\/span>\n\n\n\n

\u0628\u0631\u0627\u06cc \u0633\u0627\u062e\u062a\u0646 \u0631\u0627\u0628\u0637\u0647 \u0647\u0627\u06cc \u0639\u0645\u0648 \u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0631\u0627\u0633 \u0645\u062b\u0644 u<\/span> \u0628\u0627\u06cc\u062f f_{A,B,amoo}<\/span> \u0631\u0627 \u0627\u062c\u0631\u0627 \u06a9\u0646\u06cc\u0645:<\/p>\n\n\nB={sons_u}<\/span>\n\n\n\nA={sons_{sons_u}}<\/span>\n\n\n\n

\u062a\u0639\u062f\u0627\u062f \u0631\u0627\u0633 \u0647\u0627\u06cc \u06af\u0631\u0627\u0641 O(n)<\/span> \u0627\u0633\u062a.\u0628\u0627 \u062a\u0648\u062c\u0647 \u0628\u0647 \u0627\u06cc\u0646\u06a9\u0647 \\sum_{u}^{} sons_u<\/span> \u062a\u0639\u062f\u0627\u062f \u0631\u0627\u0628\u0637\u0647 \u0647\u0627\u06cc \u067e\u062f\u0631 \u0648 \u067e\u0633\u0631\u06cc \u0631\u0627 \u0645\u06cc \u0634\u0645\u0627\u0631\u062f \u0648 \\sum_{u}^{} sons_{sons_u} <\/span> \u062a\u0639\u062f\u0627\u062f \u0631\u0627\u0628\u0637\u0647 \u0647\u0627\u06cc \u067e\u062f\u0631 \u0648 \u067e\u062f\u0631\u0628\u0632\u0631\u06af\u06cc \u0631\u0627 \u0645\u06cc \u0634\u0645\u0627\u0631\u062f \u0648 \u0647\u0631 \u06a9\u0633 \u062d\u062f\u0627\u06a9\u062b\u0631 \u06f2 \u067e\u062f\u0631 \u0648 \u06f4 \u067e\u062f\u0631 \u0628\u0632\u0631\u06af \u062f\u0627\u0631\u062f \u0645\u06cc\u200c\u062a\u0648\u0627\u0646 \u0646\u062a\u06cc\u062c\u0647 \u06af\u0631\u0641\u062a \u062a\u0639\u062f\u0627\u062f \u06cc\u0627\u0644\u200c\u0647\u0627\u06cc \u06af\u0631\u0627\u0641 \u0633\u0627\u062e\u062a\u0647 \u0634\u062f\u0647 \u0647\u0645 O(n) <\/span> \u0627\u0633\u062a.<\/p>\n\n\n\n

\u062d\u0627\u0644\u0627 \u062a\u0646\u0647\u0627 \u06a9\u0627\u0641\u06cc \u0627\u0633\u062a \u0628\u062a\u0648\u0627\u0646\u06cc\u0645 \u06cc\u06a9 \u06a9\u0648\u062a\u0627\u0647 \u062a\u0631\u06cc\u0646 \u0645\u0633\u06cc\u0631 \u062f\u0631 \u0627\u06cc\u0646 \u06af\u0631\u0627\u0641 \u067e\u06cc\u062f\u0627 \u06a9\u0646\u06cc\u0645 (\u200c\u0686\u0648\u0646 \u0647\u0631 \u0631\u0627\u0628\u0637\u0647 \u0627\u0632 \u0637\u06cc \u06a9\u0631\u062f\u0646 \u062f\u0648 \u06cc\u0627\u0644 \u0634\u06a9\u0644 \u0645\u06cc \u06af\u06cc\u0631\u062f \u0637\u0648\u0644 \u0627\u06cc\u0646 \u06a9\u0648\u062a\u0627\u0647 \u062a\u0631\u06cc\u0646 \u0645\u0633\u06cc\u0631 \u06f2 \u0628\u0631\u0627\u0628\u0631 \u06a9\u0648\u062a\u0627\u0647 \u062a\u0631\u06cc\u0646 \u0631\u0627\u0628\u0637\u0647 \u0627\u0633\u062a) \u06a9\u0647 \u0631\u0634\u062a\u0647 \u0645\u062a\u0646\u0627\u0638\u0631 \u0622\u0646 (\u06a9\u0647 \u0631\u0648\u06cc \u0631\u0627\u0633 \u0647\u0627 \u0631\u0634\u062a\u0647 \u0646\u0648\u0634\u062a\u06cc\u0645 \u0648 \u0631\u0634\u062a\u0647 \u0645\u062a\u0646\u0627\u0638\u0631 \u0628\u0647 \u0631\u0627\u0633 \u0647\u0627\u06cc \u0627\u0635\u0644\u06cc \u067e\u0648\u0686 \u0627\u0633\u062a) \u0627\u0632 \u0644\u062d\u0627\u0638 \u062a\u0631\u062a\u06cc\u0628 \u0644\u063a\u062a \u0646\u0627\u0645\u0647 \u0627\u06cc \u0645\u0627\u06a9\u0633\u06cc\u0645\u0645 \u0628\u0627\u0634\u062f! \u0647\u0645\u0686\u0646\u06cc\u0646 \u062a\u0648\u062c\u0647 \u06a9\u0646\u06cc\u062f \u06a9\u0647 \u06cc\u0627\u0644 \u0647\u0627 \u0628\u0631\u0639\u06a9\u0633 \u0634\u062f\u0647 \u0627\u0646\u062f \u0648 \u06a9\u0648\u062a\u0627\u0647 \u062a\u0631\u06cc\u0646 \u0645\u0633\u06cc\u0631 \u0627\u0632 b<\/span> \u0631\u0627 \u0645\u06cc \u062e\u0648\u0627\u0647\u06cc\u0645.<\/p>\n\n\n\n

\u0627\u06cc\u0646 \u06a9\u0627\u0631 \u0631\u0627 \u0628\u0627 \u06a9\u0645\u06a9 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 bfs<\/span> \u0628\u0627 \u06a9\u0645\u06cc \u062a\u063a\u06cc\u06cc\u0631 \u0627\u0646\u062c\u0627\u0645 \u0645\u06cc\u200c\u062f\u0647\u06cc\u0645. \u0628\u062f\u0648\u0646 \u062a\u0648\u062c\u0647 \u0628\u0647 \u0631\u0634\u062a\u0647 \u0631\u0648\u06cc \u0631\u0627\u0633 \u0647\u0627 bfs<\/span> \u0631\u0627 \u0628\u0627 \u0634\u0631\u0648\u0639 \u0627\u0632 \u0631\u0627\u0633 b<\/span> \u0627\u062c\u0631\u0627 \u0645\u06cc \u06a9\u0646\u06cc\u0645.\u062d\u0627\u0644\u0627 \u06af\u0631\u0627\u0641 \u0645\u0627 \u0644\u0627\u06cc\u0647 \u0628\u0646\u062f\u06cc \u0634\u062f\u0647 \u0627\u0633\u062a.\u062a\u0646\u0647\u0627 \u06cc\u0627\u0644 \u0647\u0627\u06cc\u06cc \u06a9\u0647 \u0628\u06cc\u0646 \u0644\u0627\u06cc\u0647 \u0647\u0627\u06cc \u0645\u062a\u0648\u0627\u0644\u06cc \u0647\u0633\u062a\u0646\u062f \u0631\u0627 \u0646\u06af\u0647 \u062f\u0627\u0631\u06cc\u062f \u0648 \u0628\u0642\u06cc\u0647 \u0631\u0627 \u062f\u0648\u0631 \u0628\u0631\u06cc\u0632\u06cc\u062f \u0632\u06cc\u0631\u0627 \u0628\u0631\u0627\u06cc \u0628\u0647 \u062f\u0633\u062a \u0622\u0648\u0631\u062f\u0646 \u06a9\u0648\u062a\u0627\u0647 \u062a\u0631\u06cc\u0646 \u0645\u0633\u06cc\u0631 \u0644\u0627\u0632\u0645 \u0648 \u06a9\u0627\u0641\u06cc \u0627\u0633\u062a \u06a9\u0647 \u062a\u0646\u0647\u0627 \u0627\u0632 \u0627\u06cc\u0646 \u06cc\u0627\u0644 \u0647\u0627 \u0627\u0633\u062a\u0641\u0627\u062f\u0647 \u06a9\u0646\u06cc\u0645.\u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0631\u0627\u0633 \u0645\u062b\u0644 u<\/span> \u0631\u0634\u062a\u0647 \u0645\u0627\u06a9\u0633\u06cc\u0645\u0645\u06cc \u06a9\u0647 \u0645\u06cc \u062a\u0648\u0627\u0646 \u0628\u0627 \u0637\u06cc \u06a9\u0631\u062f\u0646 \u0645\u0633\u06cc\u0631\u06cc \u0627\u0632 \u0631\u06cc\u0634\u0647 \u0628\u0647 \u0622\u0646 \u0631\u0627\u0633 \u0633\u0627\u062e\u062a \u0631\u0627 S_u<\/span> \u0628\u0646\u0627\u0645\u06cc\u062f.\u0647\u062f\u0641 \u0627\u06cc\u0646 \u0646\u06cc\u0633\u062a \u06a9\u0647 S_u<\/span> \u0647\u0627 \u0631\u0627 \u0628\u0647 \u062f\u0633\u062a \u0622\u0648\u0631\u06cc\u0645 \u0628\u0644\u06a9\u0647 \u0627\u06cc\u0646 \u0627\u0633\u062a \u06a9\u0647 \u0628\u0641\u0647\u0645\u06cc\u0645 \u0628\u0631\u0627\u06cc \u0633\u0627\u062e\u062a\u0646 S_u<\/span> \u0631\u0627\u0633 \u0642\u0628\u0644 \u0627\u0632 u<\/span> \u062f\u0631 \u0645\u0633\u06cc\u0631 \u06a9\u0647 \u0628\u0648\u062f\u0647 \u0627\u0633\u062a.( \u06a9\u0647 \u062f\u0631 \u0644\u0627\u06cc\u0647 \u0642\u0628\u0644\u06cc \u0627\u0633\u062a) \u0632\u06cc\u0631\u0627 \u0627\u06af\u0631 \u0627\u06cc\u0646 \u0631\u0627 \u0628\u0641\u0647\u0645\u06cc\u0645 \u0645\u06cc \u062a\u0648\u0627\u0646\u06cc\u0645 \u0645\u0633\u06cc\u0631 \u0645\u0648\u0631\u062f \u0646\u0638\u0631 \u0631\u0627 \u0628\u0633\u0627\u0632\u06cc\u0645.<\/p>\n\n\n\n

\u0628\u0631\u0627\u06cc \u0627\u06cc\u0646 \u06a9\u0627\u0631 \u062a\u0646\u0647\u0627 \u0644\u0627\u0632\u0645 \u0627\u0633\u062a \u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0631\u0627\u0633 \u0645\u062b\u0644 u<\/span> \u0639\u062f\u062f\u06cc \u0645\u062b\u0644 rank<\/span> \u0645\u062d\u0627\u0633\u0628\u0647 \u06a9\u0646\u06cc\u0645 \u06a9\u0647 \u0646\u0634\u0627\u0646 \u0645\u06cc \u062f\u0647\u062f \u0627\u06af\u0631 \u0644\u0627\u06cc\u0647 \u0645\u0631\u0628\u0648\u0637 \u0628\u0647 u<\/span> \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u0645 \u0631\u0634\u062a\u0647 S_u<\/span> \u0627\u0632 \u0644\u062d\u0627\u0638 \u0628\u0632\u0631\u06af\u06cc \u0686\u0646\u062f\u0645\u06cc\u0646 \u0631\u0634\u062a\u0647 \u062f\u0631 \u0627\u06cc\u0646 \u0644\u0627\u06cc\u0647 \u0627\u0633\u062a.(\u200c\u0648 \u0627\u06af\u0631 S_i=S_j<\/span> \u0628\u0648\u062f \u0622\u0646\u06af\u0627\u0647 rank_i=rank_j<\/span>). \u062d\u0627\u0644\u0627 \u0627\u06af\u0631 rank<\/span> \u0631\u0627\u0633 \u0647\u0627\u06cc \u0644\u0627\u06cc\u0647 \u0642\u0628\u0644\u06cc \u0631\u0627 \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u06cc\u0645 \u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0631\u0627\u0633 \u0645\u062b\u0644 u<\/span> \u062f\u0631 \u0644\u0627\u06cc\u0647 \u0641\u0639\u0644\u06cc \u0645\u06cc \u062a\u0648\u0627\u0646 \u0628\u0647 \u062f\u0633\u062a \u0622\u0648\u0631\u062f \u06a9\u0647 \u0631\u0627\u0633 \u0642\u0628\u0644 \u0627\u0632 \u0622\u0646 \u0628\u0627\u06cc\u062f \u0686\u0647 \u06a9\u0633\u06cc \u0628\u0627\u0634\u062f.( \u06cc\u06a9\u06cc \u0631\u0627\u0633\u06cc \u06a9\u0647 rank<\/span> \u0622\u0646 \u0628\u06cc\u0634\u06cc\u0646\u0647 \u0627\u0633\u062a).\u067e\u0633 \u062a\u0646\u0647\u0627 \u06a9\u0627\u0641\u06cc \u0627\u0633\u062a \u0628\u062a\u0648\u0627\u0646\u06cc\u0645 \u0628\u0627 \u062f\u0627\u0634\u062a\u0646 rank<\/span> \u0647\u0627\u06cc \u0644\u0627\u06cc\u0647 \u0642\u0628\u0644\u06cc rank<\/span> \u0647\u0627\u06cc \u0644\u0627\u06cc\u0647 \u062c\u062f\u06cc\u062f \u0631\u0627 \u0628\u0633\u0627\u0632\u06cc\u0645!\u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0631\u0627\u0633 \u0645\u062b\u0644 u<\/span> \u062f\u0631 \u0644\u0627\u06cc\u0647 \u0641\u0639\u0644\u06cc \u0628\u06cc\u0646 \u062a\u0645\u0627\u0645 \u0631\u0627\u0633 \u0647\u0627\u06cc\u06cc \u0644\u0627\u06cc\u0647 \u0642\u0628\u0644\u06cc \u06a9\u0647 \u0628\u0647 u<\/span> \u06cc\u0627\u0644 \u062f\u0627\u0631\u0646\u062f \u0631\u0627\u0633\u06cc \u0645\u062b\u0644 y<\/span> \u0631\u0627 \u0628\u06cc\u0627\u0628\u06cc\u062f \u06a9\u0647 rank_y<\/span> \u0645\u0627\u06a9\u0633\u06cc\u0645\u0645 \u0628\u0627\u0634\u062f.\u062d\u0627\u0644\u0627 \u0628\u0647 \u0627\u0632\u0627\u06cc \u062a\u0645\u0627\u0645 \u0631\u0627\u0633 \u0647\u0627\u06cc \u0644\u0627\u06cc\u0647 \u062c\u062f\u06cc\u062f \u0645\u062b\u0644 u<\/span> \u0642\u0631\u0627\u0631 \u062f\u0647\u06cc\u062f:<\/p>\n\n\nval_u = pair<rank_y,string_u><\/span>\n\n\n\n

\u0627\u06af\u0631 val<\/span> \u0645\u0631\u0628\u0648\u0637 \u0628\u0647 \u062a\u0645\u0627\u0645 \u0631\u0627\u0633 \u0647\u0627\u06cc \u0644\u0627\u06cc\u0647 \u062c\u062f\u06cc\u062f \u0631\u0627 \u0645\u0631\u062a\u0628 \u06a9\u0646\u06cc\u062f \u0645\u06cc \u062a\u0648\u0627\u0646 \u0627\u0632 \u0631\u0648\u06cc \u0622\u0646 rank<\/span> \u0647\u0627\u06cc \u0644\u0627\u06cc\u0647 \u062c\u062f\u06cc\u062f \u0631\u0627 \u0628\u0647 \u062f\u0633\u062a \u0622\u0648\u0631\u062f. \u067e\u0633 \u0631\u0627\u0647 \u062d\u0644 \u0645\u0627 O(n*log(n))<\/span> \u0645\u06cc \u0628\u0627\u0634\u062f.\u0642\u0627\u0628\u0644 \u0630\u06a9\u0631 \u0627\u0633\u062a \u06a9\u0647 \u0628\u0647 \u0631\u0627\u062d\u062a\u06cc \u0645\u06cc \u062a\u0648\u0627\u0646 \u062d\u0644 \u0628\u0627\u0644\u0627 \u0631\u0627 O(n)<\/span> \u06a9\u0631\u062f<\/p>\n\n\n\n

\u0631\u0645\u0632 \u062c\u0627\u06cc\u06af\u0634\u062a<\/a><\/p>\n\n\n\n


\u0627\u0628\u062a\u062f\u0627 \u0635\u0648\u0631\u062a \u0633\u0648\u0627\u0644 \u0631\u0627 \u062f\u0642\u06cc\u0642 \u062a\u0631 \u0628\u06cc\u0627\u0646 \u0645\u06cc \u06a9\u0646\u06cc\u0645.\u06cc\u06a9 \u062c\u0627\u06cc\u06af\u0634\u062a n <\/span> \u062a\u0627\u06cc\u06cc \u062f\u0627\u0631\u06cc\u0645. m <\/span> \u062a\u0627 \u062c\u0627\u06cc\u06af\u0634\u062a \u062f\u06cc\u06af\u0631 \u0647\u0645 \u062f\u0627\u0631\u06cc\u0645 \u06a9\u0647 \u0645\u062c\u0645\u0648\u0639 \u0627\u0646\u062f\u0627\u0632\u0647 \u0647\u0627\u06cc \u0622\u0646\u0647\u0627 \u0631\u0627 \u0628\u0627 \\sigma <\/span> ( \u0628\u062e\u0648\u0627\u0646\u06cc\u062f \u0633\u06cc\u06af\u0645\u0627) \u0646\u0634\u0627\u0646 \u0645\u06cc \u062f\u0647\u06cc\u0645.\u06cc\u0647 \u06cc\u06a9 \u0628\u0627\u0632\u0647 \u0627\u0632 \u062c\u0627\u06cc\u06af\u0634\u062a \u0627\u0635\u0644\u06cc \u062e\u0648\u0628 \u0645\u06cc \u06af\u0648\u06cc\u06cc\u0645 \u0627\u06af\u0631 \u0641\u0634\u0631\u062f\u0647 \u0634\u062f\u0647 \u0627\u0639\u062f\u0627\u062f \u0622\u0646 \u0628\u0631\u0627\u0628\u0631 \u0628\u0627 \u06cc\u06a9\u06cc \u0627\u0632 m <\/span> \u062c\u0627\u06cc\u06af\u0634\u062a \u0628\u0627\u0634\u062f.\u062d\u0627\u0644\u0627 \u0645\u0627 \u0628\u0627\u06cc\u062f \u062a\u0639\u062f\u0627\u062f \u0631\u0627\u0647 \u0647\u0627\u06cc \u0627\u0641\u0631\u0627\u0632 \u062c\u0627\u06cc\u06af\u0634\u062a \u0627\u0635\u0644\u06cc \u0628\u0647 \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc \u062e\u0648\u0628 \u0631\u0627 \u0628\u06af\u0648\u06cc\u06cc\u0645.
\u0627\u062f\u0639\u0627 \u0645\u06cc \u06a9\u0646\u06cc\u0645 \u062a\u0639\u062f\u0627\u062f \u0637\u0648\u0644 \u0647\u0627\u06cc \u0645\u062e\u062a\u0644\u0641 \u062f\u0631 m<\/span> \u062c\u0627\u06cc\u06af\u0634\u062a\u0645\u0627\u0646 \u0627\u0632 O(\\sqrt{\\sigma})<\/span> \u0627\u0633\u062a.\u06a9\u0647 \u062f\u0631 \u0627\u06cc\u0646\u0635\u0648\u0631\u062a \u0645\u06cc \u062a\u0648\u0627\u0646 \u0646\u062a\u06cc\u062c\u0647 \u06af\u0631\u0641\u062a \u062a\u0639\u062f\u0627\u062f \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc \u062e\u0648\u0628 \u0627\u0632 O(n \\sqrt{\\sigma}) <\/span> \u0627\u0633\u062a.\u062d\u0627\u0644\u0627 \u0627\u06af\u0631 \u0628\u062a\u0648\u0627\u0646\u06cc\u0645 \u062a\u0645\u0627\u0645 \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc \u062e\u0648\u0628 \u0631\u0627 \u0634\u0646\u0627\u0633\u0627\u06cc\u06cc \u06a9\u0646\u06cc\u0645 \u0645\u06cc \u062a\u0648\u0627\u0646\u06cc\u0645 \u0628\u0647 \u0631\u0627\u062d\u062a\u06cc \u062c\u0648\u0627\u0628 \u0631\u0627 \u0628\u0647 \u062f\u0633\u062a \u0628\u06cc\u0627\u0631\u06cc\u0645.(\u06a9\u0627\u0641\u06cc\u0633\u062a <\/em> dp_i <\/span> \u0631\u0627 \u062a\u0639\u062f\u0627\u062f \u0627\u0641\u0631\u0627\u0632 i \u0639\u0636\u0648 \u0627\u0648\u0644 \u062c\u0627\u06cc\u06af\u0634\u062a \u0627\u0635\u0644\u06cc \u0628\u0647 \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc \u062e\u0648\u0628 \u062a\u0639\u0631\u06cc\u0641 \u06a9\u0646\u06cc\u0645 \u0648 \u062c\u0648\u0627\u0628 <\/em> dp_n <\/span> \u0627\u0633\u062a\u200c). \u0628\u0631\u0627\u06cc \u0634\u0646\u0627\u0633\u0627\u06cc\u06cc \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc \u062e\u0648\u0628 \u062f\u0648 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u0645\u06cc \u062f\u0647\u06cc\u0645. \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u0627\u0648\u0644 \u0627\u0632 <\/em> O(n\\ MaxLen\\ lg(n))<\/span> \u06a9\u0627\u0631 \u0645\u06cc \u06a9\u0646\u062f(MaxLen<\/span> \u0645\u0627\u06a9\u0633\u06cc\u0645\u0645 \u0637\u0648\u0644 \u062f\u0631 \u0622\u0646 m<\/span> \u062c\u0627\u06cc\u06af\u0634\u062a \u0627\u0633\u062a) \u0648 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u062f\u0648\u0645 \u0627\u0632 O((\\sigma+(nm))\\times lg(n)) <\/span>\u06a9\u0627\u0631 \u0645\u06cc \u06a9\u0646\u062f.\u0633\u067e\u0633 \u0628\u0627 \u062a\u0631\u06a9\u06cc\u0628 \u0627\u06cc\u0646 \u062f\u0648 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u0645\u0633\u0627\u0644\u0647 \u0627\u0632 O(n \\sqrt{\\sigma} lg(n) ) <\/span> \u062d\u0644 \u0645\u06cc \u0634\u0648\u062f.(\u06a9\u0627\u0641\u06cc\u0633\u062a \u0622\u0646 m<\/span> \u062c\u0627\u06cc\u06af\u0634\u062a \u0631\u0627 \u0628\u0647 \u062f\u0648 \u062f\u0633\u062a\u0647 \u0628\u0627 \u0637\u0648\u0644 \u06a9\u0645\u062a\u0631 \u0627\u0632 \\sqrt{\\sigma} <\/span>\u0648 \u0628\u06cc\u0634\u062a\u0631 \u0627\u0632 \u0622\u0646 \u062a\u0642\u0633\u06cc\u0645 \u06a9\u0646\u06cc\u062f \u0648 \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc \u062e\u0648\u0628\u06cc \u06a9\u0647 \u0647\u0631 \u062f\u0633\u062a\u0647 \u0645\u06cc \u0633\u0627\u0632\u062f \u0631\u0627 \u0645\u062d\u0627\u0633\u0628\u0647 \u06a9\u0646\u06cc\u0645).<\/p>\n\n\n\n

\u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u0627\u0648\u0644:<\/p>\n\n\n\n

\u0642\u0628\u0644 \u0627\u0632 \u0634\u0631\u0648\u0639 \u0628\u0647 \u0627\u06cc\u0646 \u062a\u0628\u062f\u06cc\u0644 \u062c\u0627\u06cc\u06af\u0634\u062a\u06cc \u062a\u0648\u062c\u0647 \u06a9\u0646\u06cc\u062f:
\u0641\u0631\u0636 \u06a9\u0646\u06cc\u062f \u062c\u0627\u06cc\u06af\u0634\u062a k<\/span> \u0639\u0636\u0648\u06cc p<\/span> \u0631\u0627 \u062f\u0627\u0631\u06cc\u0645 \u0648 \u0627\u06cc\u0646 \u062a\u0628\u062f\u06cc\u0644 \u0628\u0647 \u0645\u0627 \u0622\u0631\u0627\u06cc\u0647 k<\/span> \u062a\u0627\u06cc\u06cc a<\/span> \u0631\u0627 \u0645\u06cc\u062f\u0647\u062f \u06a9\u0647 :<\/p>\n\n\n\n

a_i<\/span> \u062a\u0639\u062f\u0627\u062f \u0627\u0646\u062f\u06cc\u0633 \u0647\u0627\u06cc j \\leq\\ i<\/span> \u06a9\u0647 a_j \\leq\\ a_i <\/span>
\u0628\u0647 \u0627\u06cc\u0646 \u0641\u0631\u0645 \u0627\u0632 \u0646\u0645\u0627\u06cc\u0634 \u062c\u0627\u06cc\u06af\u0634\u062a \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628 \u0645\u06cc \u06af\u0648\u06cc\u06cc\u0645.\u0645\u06cc \u062a\u0648\u0627\u0646 \u062b\u0627\u0628\u062a \u06a9\u0631\u062f \u0628\u06cc\u0646 \u062c\u0627\u06cc\u06af\u0634\u062a \u0647\u0627\u06cc k<\/span> \u062a\u0627\u06cc\u06cc p<\/span> \u0628\u0647 \u0622\u0631\u0627\u06cc\u0647 \u0647\u0627\u06cc k<\/span> \u062a\u0627\u06cc\u06cc a<\/span> \u06a9\u0647 ( 1 \\leq\\ a_i \\leq\\ i <\/span>) \u062a\u0646\u0627\u0638\u0631 \u06cc\u06a9 \u0628\u0647 \u06cc\u06a9 \u0628\u0631\u0642\u0631\u0627\u0631 \u0627\u0633\u062a \u067e\u0633 \u0647\u0631 \u062c\u0627\u06cc\u06af\u0634\u062a \u06cc\u06a9 \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628 \u062f\u0627\u0631\u062f \u0648 \u0647\u0631 \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628 \u0645\u0639\u0627\u062f\u0644 \u06cc\u06a9 \u062c\u0627\u06cc\u06af\u0634\u062a \u0627\u0633\u062a!<\/p>\n\n\n\n

\u062d\u0627\u0644\u0627 \u062a\u0648\u062c\u0647 \u06a9\u0646\u06cc\u062f \u06a9\u0647 \u0647\u0631 \u0622\u0631\u0627\u06cc\u0647 \u0628\u0627 \u0627\u0639\u062f\u0627\u062f \u0645\u062a\u0645\u0627\u06cc\u0632 \u0647\u0645 \u06cc\u06a9 \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628 \u062f\u0627\u0631\u062f.(\u062f\u0642\u06cc\u0642\u0627 \u0645\u0634\u0627\u0628\u0647 \u0628\u0627\u0644\u0627 \u062a\u0639\u0631\u06cc\u0641 \u0645\u06cc \u0634\u0648\u062f).
\u062d\u0627\u0644\u0627 \u062a\u0648\u062c\u0647 \u06a9\u0646\u06cc\u062f \u06a9\u0647 \u0641\u0634\u0631\u062f\u0647 \u0622\u0631\u0627\u06cc\u0647 a<\/span> \u0628\u0631\u0627\u0628\u0631 \u0628\u0627 \u062c\u0627\u06cc\u06af\u0634\u062a p<\/span> \u0645\u06cc \u0634\u0648\u062f \u0627\u06af\u0631 \u0648 \u0641\u0642\u0637 \u0627\u06af\u0631 \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628 \u0622\u0646 \u062f\u0648 \u0628\u0631\u0627\u0628\u0631 \u0628\u0627\u0634\u062f.
\u062d\u0627\u0644\u0627 \u06a9\u0644 m<\/span> \u062c\u0627\u06cc\u06af\u0634\u062a \u0631\u0627 \u0628\u0647 \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628 \u062f\u0631 \u0628\u06cc\u0627\u0648\u0631\u06cc\u062f(\u0627\u06cc\u0646 \u06a9\u0627\u0631 \u0627\u0632 O(\\sigma lg(n)) <\/span> \u0628\u0627 \u062f\u0627\u062f\u0647 \u0633\u0627\u062e\u062a\u0627\u0631\u06cc \u0645\u062b\u0644 \u062f\u0631\u062e\u062a \u0641\u0646\u0648\u06cc\u06a9 \u0645\u0645\u06a9\u0646 \u0627\u0633\u062a).\u0633\u067e\u0633 \u0622\u0646\u0647\u0627 \u0631\u0627 \u062f\u0631 \u062a\u0631\u0627\u06cc \u0628\u0631\u06cc\u0632\u06cc\u062f.\u062d\u0627\u0644\u0627 \u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0646\u0642\u0637\u0647 \u0634\u0631\u0648\u0639 \u0627\u0632 \u062c\u0627\u06cc\u06af\u0634\u062a \u0627\u0635\u0644\u06cc \u0645\u06cc \u062e\u0648\u0627\u0647\u06cc\u0645 \u0686\u06a9 \u06a9\u0646\u06cc\u0645 \u06a9\u0647 \u0647\u0631 \u06a9\u062f\u0627\u0645 \u0627\u0632 \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc [i,i+MaxLen) <\/span> \u062e\u0648\u0628 \u0647\u0633\u062a\u0646\u062f \u06cc\u0627 \u0646\u0647.\u0628\u0631\u0627\u06cc \u0627\u06cc\u0646\u06a9\u0627\u0631 \u0627\u0632 i<\/span> \u0634\u0631\u0648\u0639 \u0645\u06cc \u06a9\u0646\u06cc\u0645 \u0648 \u067e\u06cc\u0645\u0627\u06cc\u0634 \u0631\u0627 \u0634\u0631\u0648\u0639 \u0645\u06cc \u06a9\u0646\u06cc\u0645.\u0641\u0631\u0636 \u0645\u0631\u062d\u0644\u0647 \u0642\u0628\u0644 \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628 \u0628\u0627\u0632\u0647 [i,i+k) <\/span> \u0631\u0627 \u0633\u0627\u062e\u062a\u0647 \u0627\u06cc\u0645 \u0648 \u0645\u06a9\u0627\u0646 \u0622\u0646 \u0631\u0634\u062a\u0647 \u0631\u0627 \u062f\u0631 \u062a\u0631\u0627\u06cc \u067e\u06cc\u062f\u0627 \u06a9\u0631\u062f\u0647 \u0627\u06cc\u0645.\u062f\u0631 \u0627\u06cc\u0646 \u0645\u0631\u062d\u0644\u0647 \u0628\u0627\u06cc\u062f \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628 \u0631\u0627 \u06af\u0633\u062a\u0631\u0634 \u062f\u0647\u06cc\u0645 \u0648 \u0622\u0646\u0631\u0627 \u0628\u0631\u0627\u06cc \u0628\u0627\u0632\u0647 [i,i+k+1) <\/span> \u0628\u0633\u0627\u0632\u06cc\u0645(\u0627\u0632 \u0648\u06cc\u0698\u06af\u06cc \u0647\u0627\u06cc \u062e\u0648\u0628 \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628 \u0627\u06cc\u0646 \u0627\u0633\u062a \u06a9\u0647 \u0627\u06af\u0631 \u0628\u062e\u0648\u0627\u0647\u06cc\u0645 \u0628\u0647 \u062a\u0647 \u0622\u0631\u0627\u06cc\u0647 k<\/span> \u0639\u0636\u0648\u06cc \u0639\u062f\u062f \u0627\u0636\u0627\u0641\u0647 \u06a9\u0646\u06cc\u0645 \u062f\u06cc\u06af\u0631 k<\/span> \u0639\u0636\u0648 \u0627\u0648\u0644 \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628 \u062a\u063a\u06cc\u06cc\u0631\u06cc \u0646\u0645\u06cc \u06a9\u0646\u0646\u062f). \u0648 \u0645\u06a9\u0627\u0646 \u0631\u0634\u062a\u0647 \u062c\u062f\u06cc\u062f \u0631\u0627 \u062f\u0631 \u062a\u0631\u0627\u06cc \u067e\u06cc\u062f\u0627 \u06a9\u0646\u06cc\u0645(\u06a9\u0627\u0641\u06cc\u0633\u062a \u0627\u0632 \u0645\u06a9\u0627\u0646 \u0642\u0628\u0644\u06cc \u06cc\u0627\u0644\u06cc \u0631\u0627 \u0637\u06cc \u06a9\u0646\u06cc\u0645 \u06a9\u0647 \u0639\u062f\u062f \u0631\u0648\u06cc \u0622\u0646 \u0647\u0645\u0627\u0646 \u0639\u062f\u062f\u06cc \u0627\u0633\u062a \u06a9\u0647 \u0628\u0647 \u062a\u0647 \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628 \u0627\u0636\u0627\u0641\u0647 \u06a9\u0631\u062f\u06cc\u0645).
\u0627\u06af\u0631 \u0631\u0648\u06cc \u0631\u0627\u0633 \u0647\u0627\u06cc \u0645\u0631\u0628\u0648\u0637 \u0628\u0647 m<\/span> \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628(\u0628\u0647 \u0635\u0648\u0631\u062a \u06a9\u0627\u0645\u0644 \u0646\u0647 \u06cc\u06a9 \u067e\u0631\u06cc\u0641\u06cc\u06a9\u0633 \u0627\u0632 \u0622\u0646\u0647\u0627)\u0639\u0644\u0627\u0645\u062a \u0628\u06af\u0630\u0627\u0631\u06cc\u0645 \u0645\u06cc \u062a\u0648\u0627\u0646\u06cc\u0645 \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc \u062e\u0648\u0628 \u0628\u0627 \u0634\u0631\u0648\u0639 \u0627\u0632 i<\/span> \u0631\u0627 \u062a\u0634\u062e\u06cc\u0635 \u062f\u0647\u06cc\u0645(\u0647\u0631 \u0648\u0642\u062a \u0628\u0647 \u06cc\u06a9 \u0631\u0627\u0633 \u0639\u0644\u0627\u0645\u062a \u062f\u0627\u0631 \u0631\u0633\u06cc\u062f\u06cc\u0645 \u06cc\u0639\u0646\u06cc \u0628\u0627\u0632\u0647 \u0645\u0627\u0646 \u062e\u0648\u0628 \u0627\u0633\u062a).
\u0627\u0632 \u0622\u0646\u062c\u0627\u06cc\u06cc \u06a9\u0647 \u0627\u0632 \u0647\u0631 \u0646\u0642\u0637\u0647 \u0634\u0631\u0648\u0639 \u06a9\u0627\u0641\u06cc\u0633\u062a MaxLen<\/span> \u062a\u0627 \u062c\u0644\u0648 \u0628\u0631\u0648\u06cc\u0645 \u0648 \u0647\u0631 \u0645\u0631\u062d\u0644\u0647 \u062c\u0644\u0648 \u0631\u0641\u062a\u0646 \u0628\u0647 \u0627\u0646\u062f\u0627\u0632\u0647 O(lg(n)) <\/span>\u0628\u0631\u0627\u06cc\u0645\u0627\u0646 \u0647\u0632\u06cc\u0646\u0647 \u062f\u0627\u0631\u062f(\u06a9\u0627\u0631 \u06a9\u0631\u062f\u0646 \u0628\u0627 \u0641\u0646\u0648\u06cc\u06a9) \u067e\u0633 \u0628\u0627 \u0627\u06cc\u0646 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u0645\u06cc \u062a\u0648\u0627\u0646 \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc \u062e\u0648\u0628 \u0631\u0627 \u0627\u0632 O(n\\ MaxLen\\ lg(n))<\/span> \u067e\u06cc\u062f\u0627 \u06a9\u0631\u062f.<\/p>\n\n\n\n

\u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u062f\u0648\u0645:<\/p>\n\n\n\n

\u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u06a9\u062f\u0627\u0645 \u0627\u0632 m<\/span> \u062c\u0627\u06cc\u06af\u0634\u062a \u0686\u06a9 \u0645\u06cc \u06a9\u0646\u06cc\u0645 \u06a9\u0647 \u0628\u0627 \u0686\u0647 \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc\u06cc \u0627\u0632 \u062c\u0627\u06cc\u06af\u0634\u062a \u0627\u0635\u0644\u06cc \u0645\u0637\u0627\u0628\u0642\u062a \u062f\u0627\u0631\u062f.
\u0628\u0647 \u062c\u0627\u06cc\u06af\u0634\u062a \u0627\u0635\u0644\u06cc A<\/span> \u0648 \u0628\u0647 \u062c\u0627\u06cc\u06af\u0634\u062a\u06cc \u06a9\u0647 \u0645\u06cc \u062e\u0648\u0627\u0647\u06cc\u0645 \u0645\u06a9\u0627\u0646 \u0647\u0627\u06cc \u0645\u0646\u0637\u0628\u0642 \u0634\u062f\u0646\u0634 \u0628\u0631 \u062c\u0627\u06cc\u06af\u0634\u062a \u0627\u0635\u0644\u06cc \u0631\u0627 \u0628\u06cc\u0627\u0628\u06cc\u0645 B<\/span> \u0645\u06cc \u06af\u0648\u06cc\u06cc\u0645.
\u0645\u0634\u0627\u0628\u0647 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 KMP<\/span> \u0628\u0631\u0627\u06cc \u062a\u0637\u0627\u0628\u0642 \u0631\u0634\u062a\u0647 \u0647\u0627 \u06a9\u0627\u0631 \u0645\u06cc \u06a9\u0646\u06cc\u0645.\u062a\u0639\u0631\u06cc\u0641 \u06a9\u0646\u06cc\u062f f_i <\/span> \u0628\u0632\u0631\u06af\u062a\u0631\u06cc\u0646 \u0637\u0648\u0644 \u06a9\u0645\u062a\u0631 \u0627\u0632 i<\/span> \u0628\u0627\u0634\u062f \u06a9\u0647 \u0641\u0634\u0631\u062f\u0647 B_{1...f_i} <\/span> \u0647\u0645\u0627\u0646 \u0641\u0634\u0631\u062f\u0647 B_{i-f_i+1...i} <\/span> \u0628\u0627\u0634\u062f.\u062a\u0648\u062c\u0647 \u06a9\u0646\u06cc\u062f \u06a9\u0647 \u0628\u0631\u0627\u06cc \u0627\u06cc\u0646\u06a9\u0647 \u0627\u06cc\u0646 \u0628\u0631\u0642\u0631\u0627\u0631 \u0628\u0627\u0634\u062f \u0628\u0627\u06cc\u062f \u0641\u0634\u0631\u062f\u0647 B_{1...f_i-1} <\/span> \u0647\u0645\u0627\u0646 \u0641\u0634\u0631\u062f\u0647 B_{i-f_i+1...i-1} <\/span> \u0628\u0627\u0634\u062f \u0648 \u0647\u0645\u0686\u0646\u06cc\u0646 \u062a\u0639\u062f\u0627\u062f \u0627\u0639\u062f\u0627\u062f \u06a9\u0645\u062a\u0631 \u0645\u0633\u0627\u0648\u06cc B_i <\/span> \u062f\u0631 [i -f_i+1,i) <\/span> \u0628\u0631\u0627\u0628\u0631 \u0628\u0627 \u062a\u0639\u062f\u0627\u062f \u0627\u0639\u062f\u0627\u062f \u06a9\u0645\u062a\u0631 \u0645\u0633\u0627\u0648\u06cc B_{f_i} <\/span> \u062f\u0631 [1,f_i) <\/span>\u0628\u0627\u0634\u062f(\u0645\u06cc \u062a\u0648\u0627\u0646 \u0628\u0627 \u06a9\u0645\u06a9 \u0641\u0646\u0648\u06cc\u06a9 \u0627\u06cc\u0646 \u0631\u0627 \u0686\u06a9 \u06a9\u0631\u062f).
\u067e\u0633 \u0645\u06cc \u062a\u0648\u0627\u0646 f<\/span> \u0647\u0627 \u0631\u0627 \u0628\u0647 \u0634\u06cc\u0648\u0647 KMP<\/span> \u0628\u0647 \u062f\u0633\u062a \u0622\u0648\u0631\u062f.
\u0647\u0645\u0686\u0646\u06cc\u0646 match_i<\/span> \u0631\u0627 \u062a\u0639\u0631\u06cc\u0641 \u0645\u06cc \u06a9\u0646\u06cc\u0645 \u0645\u0627\u06a9\u0633\u06cc\u0645\u0645 \u0645\u0642\u062f\u0627\u0631\u06cc \u06a9\u0647 \u0641\u0634\u0631\u062f\u0647 A_{i-match_i+1...i}<\/span> \u0647\u0645\u0627\u0646 \u0641\u0634\u0631\u062f\u0647 B_{1...match_i}<\/span> \u0628\u0627\u0634\u062f.\u0645\u0634\u0627\u0628\u0647 \u0628\u0627\u0644\u0627 \u0648 \u0628\u0627 \u062a\u0648\u062c\u0647 \u0628\u0647 \u0634\u06cc\u0648\u0647 \u06a9\u0627\u0631 KMP<\/span> \u0645\u06cc \u062a\u0648\u0627\u0646 match<\/span> \u0647\u0627 \u0631\u0627 \u0647\u0645 \u0628\u0647 \u062f\u0633\u062a \u0622\u0648\u0631\u062f \u06a9\u0647 \u0627\u06cc\u0646\u06a9\u0627\u0631 \u0627\u0632 O((|A|+|B|)lg(|A|+|B|)) <\/span> \u0627\u0646\u062c\u0627\u0645 \u0645\u06cc \u0634\u0648\u062f(\u0648 \u062f\u0631 \u0646\u0647\u0627\u06cc\u062a \u0645\u06a9\u0627\u0646 \u0647\u0627\u06cc\u06cc \u06a9\u0647 match_i = |B| <\/span> \u0627\u0633\u062a \u0631\u0627 \u0645\u06cc \u062e\u0648\u0627\u0647\u06cc\u0645).<\/p>\n\n\n\n

\u0633\u0648\u0627\u0644\u0627\u062a \u062a\u0631\u06a9\u06cc\u0628\u06cc:<\/a><\/p>\n\n\n\n


\u0627\u062f\u0639\u0627 \u0645\u06cc \u06a9\u0646\u06cc\u0645<\/a> \u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0639\u062f\u062f \u0627\u0648\u0644 p<\/span> \u0639\u062f\u062f\u06cc \u0645\u062b\u0644 g<\/span> \u0648\u062c\u0648\u062f \u062f\u0627\u0631\u062f \u06a9\u0647 g^1...g^{p-1} <\/span> \u062a\u0645\u0627\u0645 \u0628\u0627\u0642\u06cc \u0645\u0627\u0646\u062f\u0647 \u0647\u0627\u06cc \u0645\u0645\u06a9\u0646 \u0628\u0647 \u067e\u06cc\u0645\u0627\u0646\u0647 p<\/span> \u0631\u0627 \u062a\u0648\u0644\u06cc\u062f \u0645\u06cc \u06a9\u0646\u0646\u062f.
\u0628\u0647 \u0686\u0646\u06cc\u0646 g<\/span> \u0647\u0627\u06cc\u06cc \u0631\u06cc\u0634\u0647 \u0627\u0648\u0644\u06cc\u0647 p<\/span> \u0645\u06cc \u06af\u0648\u06cc\u06cc\u0645(\u062f\u0631 \u0627\u0646\u062a\u0647\u0627 \u0631\u0648\u0634 \u0628\u0647 \u062f\u0633\u062a \u0627\u0648\u0631\u062f\u0646 \u0631\u06cc\u0634\u0647 \u0627\u0648\u0644\u06cc\u0647 \u0631\u0627 \u062a\u0648\u0636\u06cc\u062d \u0645\u06cc \u062f\u0647\u06cc\u0645).
\u062d\u0627\u0644\u0627 \u0641\u0631\u0636 \u06a9\u0646\u06cc\u062f g<\/span> \u0631\u0627 \u06cc\u0627\u0641\u062a\u0647 \u0627\u06cc\u0645.\u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0639\u062f\u062f \u0628\u06cc\u0646 1<\/span> \u062a\u0627 p-1<\/span> \u0628\u0647 \u062f\u0633\u062a \u0622\u0648\u0631\u06cc\u062f \u06a9\u0647 \u0645\u0639\u0627\u062f\u0644 \u0686\u0647 \u062a\u0648\u0627\u0646\u06cc \u0627\u0632 g<\/span> \u0627\u0633\u062a \u0627\u06cc\u0646 \u0645\u0642\u062f\u0627\u0631 \u0631\u0627 \u0628\u0631\u0627\u06cc \u0639\u062f\u062f x<\/span> \u0628\u0627 log_x<\/span> \u0646\u0634\u0627\u0646 \u0645\u06cc\u200c\u062f\u0647\u06cc\u0645.
\u062d\u0627\u0644\u0627 \u062a\u0648\u062c\u0647 \u06a9\u0646\u06cc\u062f \u06a9\u0647
log_{x*y} \\equiv log_x+log_y \\mod p-1 <\/span><\/p>\n\n\n\n

\u062d\u0627\u0644\u0627 \u0627\u06af\u0631 \u0628\u0647 \u062c\u0627\u06cc \u0647\u0631 \u0639\u062f\u062f log<\/span> \u0627\u0634 \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u0645 \u0639\u0645\u0644\u06cc\u0627\u062a \u0636\u0631\u0628 \u062f\u0631 \u067e\u06cc\u0645\u0627\u0646\u0647 p<\/span> \u0628\u0647 \u062c\u0645\u0639 \u062f\u0631 \u067e\u06cc\u0645\u0627\u0646\u0647 p-1<\/span> \u062a\u0628\u062f\u06cc\u0644 \u0645\u06cc \u0634\u0648\u062f!
\u067e\u0633 \u0627\u06af\u0631 \u062c\u0645\u0639 \u062a\u0645\u0627\u0645 \u0632\u06cc\u0631 \u0645\u062c\u0645\u0648\u0639\u0647 \u0647\u0627\u06cc \u0645\u0645\u06a9\u0646 \u0627\u0632 log_{a_i} <\/span> \u0647\u0627 \u062f\u0631 \u067e\u06cc\u0645\u0627\u0646\u0647 p-1<\/span> \u0631\u0627 \u0628\u0647 \u062f\u0633\u062a \u0622\u0648\u0631\u06cc\u0645 \u0622\u0646\u06af\u0627\u0647 \u062a\u0645\u0627\u0645 log_{ans} <\/span> \u0647\u0627 \u0631\u0627 \u0628\u0647 \u062f\u0633\u062a \u0627\u0648\u0631\u062f\u06cc\u0645 \u06a9\u0647 ans<\/span> \u0647\u0627 \u062c\u0648\u0627\u0628 \u0647\u0627\u06cc \u0645\u0645\u06a9\u0646 \u0647\u0633\u062a\u0646\u062f.
\u0628\u0631\u0627\u06cc \u062d\u0633\u0627\u0628 \u06a9\u0631\u062f\u0646 \u062c\u0645\u0639 \u062a\u0645\u0627\u0645 \u0632\u06cc\u0631\u0645\u062c\u0645\u0648\u0639\u0647 \u0647\u0627\u06cc \u0645\u0645\u06a9\u0646 \u0627\u0632 \u06a9\u0627\u0641\u06cc\u0633\u062a \u0628\u0647 \u0634\u06cc\u0648\u0647 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u06a9\u0648\u0644\u0647 \u067e\u0634\u062a\u06cc \u06a9\u0627\u0631 \u06a9\u0646\u06cc\u0645 \u0627\u0645\u0627 \u0628\u0627 \u0627\u06cc\u0646 \u062a\u0641\u0627\u0648\u062a \u06a9\u0647 \u0645\u06cc \u062a\u0648\u0627\u0646 \u0627\u06cc\u0646 \u06a9\u0627\u0631 \u0631\u0627 \u0628\u0627 \u0628\u06cc\u062a \u0633\u062a \u0647\u0645 \u0627\u0646\u062c\u0627\u0645 \u062f\u0627\u062f! \u06cc\u0639\u0646\u06cc \u0641\u0631\u0636 \u06a9\u0646\u06cc\u062f dp<\/span> \u0628\u06cc\u062a \u0633\u062a\u06cc \u0628\u0627\u0634\u062f \u06a9\u0647 \u0628\u06cc\u062a i<\/span> \u0627\u0645 \u0622\u0646 \u06f1 \u0627\u0633\u062a \u0627\u06af\u0631 \u0628\u062a\u0648\u0627\u0646 \u0645\u062c\u0645\u0648\u0639\u0647 \u0627\u06cc \u0628\u0627 \u062c\u0645\u0639 i<\/span> \u062f\u0627\u0634\u062a.(\u0627\u0648\u0644 \u06a9\u0627\u0631 dp_0=1<\/span>) \u062d\u0627\u0644\u0627 \u0628\u0639\u062f \u0627\u0632 \u0627\u0636\u0627\u0641\u0647 \u06a9\u0631\u062f\u0646 \u0639\u062f\u062f x<\/span> \u0628\u0647 \u0622\u0631\u0627\u06cc\u0647 \u0645\u0642\u062f\u0627\u0631 \u062c\u062f\u06cc\u062f dp<\/span> \u0628\u0631\u0627\u0628\u0631 \u0628\u0627 dp | (dp << (p-1-x) )<\/span> \u0645\u06cc \u0634\u0648\u062f \u067e\u0633 \u062f\u0631 \u0646\u0647\u0627\u06cc\u062a \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u0645\u0627 \u0627\u0632 O(\\frac{np}{32}) <\/span> \u06a9\u0627\u0631 \u0645\u06cc \u06a9\u0646\u062f.
\u0631\u0648\u0634 \u0628\u0647 \u062f\u0633\u062a \u0627\u0648\u0631\u062f\u0646 \u0631\u06cc\u0634\u0647 \u0627\u0648\u0644\u06cc\u0647:
\u0627\u0628\u062a\u062f\u0627 \u062a\u0648\u062c\u0647 \u06a9\u0646\u06cc\u062f \u06a9\u0647 \u0627\u06af\u0631 d<\/span> \u06a9\u0648\u0686\u06a9\u062a\u0631\u06cc\u0646 \u0639\u062f\u062f\u06cc \u0628\u0627\u0634\u062f \u06a9\u0647 x^d \\equiv 1\\ mod p <\/span> \u0622\u0646\u06af\u0627\u0647 \u062a\u0645\u0627\u0645 \u0627\u0639\u062f\u0627\u062f x^0 ... x^{d-1}<\/span> \u0645\u062a\u0645\u0627\u06cc\u0632\u0646\u062f(\u062f\u0631 \u063a\u06cc\u0631 \u0627\u06cc\u0646\u0635\u0648\u0631\u062a d<\/span> \u0645\u0627 \u0645\u06cc\u0646\u06cc\u0645\u0645 \u0646\u06cc\u0633\u062a).\u0627\u0632 \u0627\u06cc\u0646 \u0645\u0648\u0636\u0648\u0639 \u0646\u062a\u06cc\u062c\u0647 \u0645\u06cc \u0634\u0648\u062f \u06a9\u0647 x^y = x^{y\\ mod\\ d} <\/span> \u067e\u0633 \u0627\u06af\u0631 \u0642\u0631\u0627\u0631 \u0628\u0627\u0634\u062f \u06a9\u0647 x^y \\equiv 1 \\mod p <\/span> \u0622\u0646\u06af\u0627\u0647 \u0628\u0627\u06cc\u062f d|y<\/span>.
\u0627\u0632 \u0637\u0631\u0641\u06cc \u0637\u0628\u0642 \u0642\u0636\u06cc\u0647 \u0641\u0631\u0645\u0627 \u0645\u06cc \u062f\u0627\u0646\u06cc\u0645 \u06a9\u0647 x^{p-1} \\equiv 1 \\mod p <\/span> \u0647\u0645\u0686\u0646\u06cc\u0646 \u0637\u0628\u0642 \u062a\u0639\u0631\u06cc\u0641 \u0648 \u0645\u0637\u0627\u0644\u0628 \u0628\u0627\u0644\u0627 \u0639\u062f\u062f x<\/span> \u0631\u06cc\u0634\u0647 \u0627\u0648\u0644\u06cc\u0647 \u0627\u0633\u062a \u0627\u06af\u0631 \u0648 \u0641\u0642\u0637 \u0627\u06af\u0631 d=p-1<\/span>.
\u062a\u0648\u062c\u0647 \u06a9\u0646\u06cc\u062f \u06a9\u0647 d|p-1<\/span>.\u062d\u0627\u0644\u0627 \u0627\u06af\u0631 d\\neq p-1<\/span> \u0628\u0627\u06cc\u062f \u0639\u0627\u0645\u0644 \u0627\u0648\u0644\u06cc \u062f\u0631 p-1<\/span> \u0645\u062b\u0644 q<\/span> \u0648\u062c\u0648\u062f \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u062f \u06a9\u0647 d \\mid \\frac{p-1}{q} <\/span> \u0648 \u062f\u0631 \u0646\u062a\u06cc\u062c\u0647 x^{\\frac{p-1}{q}} \\equiv 1 \\mod p <\/span> .
\u067e\u0633 \u0645\u06cc \u062a\u0648\u0627\u0646 \u0628\u0631\u0627\u06cc \u062a\u0645\u0627\u0645 \u0639\u062f\u0627\u062f \u06f1 \u062a\u0627 p-1<\/span> \u0631\u0627 \u0686\u06a9 \u06a9\u0631\u062f \u06a9\u0647 \u0645\u06cc \u062a\u0648\u0627\u0646\u0646\u062f \u0631\u06cc\u0634\u0647 \u0627\u0648\u0644\u06cc\u0647 \u0628\u0627\u0634\u0646\u062f \u06cc\u0627 \u0646\u0647(\u0648 \u0627\u06cc\u0646 \u0641\u0631\u0627\u06cc\u0646\u062f \u0686\u06a9 \u06a9\u0631\u062f\u0646 \u0628\u0627 O(lg(p))<\/span> \u0628\u0627\u0631 \u0628\u0647 \u062a\u0648\u0627\u0646 \u0631\u0633\u0627\u0646\u062f\u0646 \u0647\u0645\u0631\u0627\u0647 \u0627\u0633\u062a). \u067e\u0633 \u0645\u06cc \u062a\u0648\u0627\u0646 \u0627\u06cc\u0646 \u06a9\u0627\u0631 \u0631\u0627 \u0627\u0632 O(g\\times lg(p)^2) <\/span> \u0627\u0646\u062c\u0627\u0645 \u062f\u0627\u062f. <\/p>\n\n\n\n

\u06a9\u067e\u06cc \u067e\u06cc\u0633\u062a:<\/a><\/p>\n\n\n\n

\u0622\u0631\u0627\u06cc\u0647 \u0631\u0627 \u062f\u0631 \u06cc\u06a9 \u062f\u0631\u062e\u062a \u062f\u0648\u062f\u0648\u06cc\u06cc \u0645\u062a\u0648\u0627\u0632\u0646 \u0645\u06cc\u0631\u06cc\u0632\u06cc\u0645 . ( \u0645\u0627\u0646\u0646\u062f AVL\\ Tree<\/span> ) . \u06cc\u06a9 \u06a9\u067e\u06cc \u0627\u0632 \u062f\u0631\u062e\u062a \u0645\u06cc \u06af\u06cc\u0631\u06cc\u0645 \u0648 \u0628\u0627\u0632\u0647 [l,r] <\/span> \u06a9\u067e\u06cc \u0631\u0627 \u0627\u0632 \u062f\u0631\u062e\u062a \u062c\u062f\u0627 \u0645\u06cc \u06a9\u0646\u06cc\u0645 (\u200c\u0627\u06cc\u0646 \u06a9\u0627\u0631 \u0627\u0632 O(h)<\/span> \u0642\u0627\u0628\u0644 \u0627\u0646\u062c\u0627\u0645 \u0627\u0633\u062a). \u0633\u067e\u0633 \u062f\u0631\u062e\u062a \u0627\u0635\u0644\u06cc \u0631\u0627 \u0627\u0632 \u0645\u06a9\u0627\u0646 k<\/span> \u0628\u0647 \u062f\u0648 \u0642\u0633\u0645\u062a \u062a\u0642\u0633\u06cc\u0645 \u0645\u06cc \u06a9\u0646\u06cc\u0645 \u0648 \u0642\u0633\u0645\u062a [l,r]<\/span> \u062f\u0631\u062e\u062a \u0642\u0628\u0644\u06cc \u0631\u0627 \u062f\u0631 \u0641\u0627\u0635\u0644\u0647 k<\/span> \u0648 k+1<\/span> \u0627\u0636\u0627\u0641\u0647 \u0645\u06cc \u06a9\u0646\u06cc\u0645.\u0641\u0642\u0637 \u0646\u0628\u0627\u06cc\u062f \u062f\u0631\u062e\u062a \u0631\u0627 \u0648\u0627\u0642\u0639\u0627 \u06a9\u067e\u06cc \u0628\u06af\u06cc\u0631\u06cc\u0645 \u0632\u06cc\u0631\u0627 \u0632\u0645\u0627\u0646 \u0627\u062c\u0631\u0627\u06cc\u06cc \u06a9\u062f \u0628\u0647 \u0635\u0648\u0631\u062a \u0646\u0645\u0627\u06cc\u06cc \u0632\u06cc\u0627\u062f \u0645\u06cc\u0634\u0648\u062f.\u0635\u0631\u0641\u0627 \u0628\u0627\u06cc\u062f \u062f\u0631 \u0647\u0631 \u0645\u0631\u062d\u0644\u0647 \u062a\u063a\u06cc\u06cc\u0631\u0627\u062a \u062f\u0631\u062e\u062a \u0642\u0628\u0644\u06cc \u0646\u0633\u0628\u062a \u0628\u0647 \u062f\u0631\u062e\u062a \u0647\u0627\u06cc \u062c\u062f\u06cc\u062f \u0631\u0627 \u0630\u062e\u06cc\u0631\u0647 \u06a9\u0646\u06cc\u0645 \u0648 \u0647\u06cc\u0686\u0648\u0642\u062a \u0628\u0647 \u062f\u0627\u062f\u0647\u200c\u0647\u0627\u06cc \u062f\u0631\u062e\u062a\u200c\u0647\u0627\u06cc \u0642\u0628\u0644\u06cc \u062f\u0633\u062a \u0646\u0632\u0646\u06cc\u0645. \u0627\u06af\u0631 \u0627\u06cc\u0646 \u06a9\u0627\u0631 \u0631\u0627 \u06a9\u0646\u06cc\u0645 \u0642\u0633\u0645\u062a \u0647\u0627\u06cc \u062a\u06a9\u0631\u0627\u0631\u06cc \u062f\u0631\u062e\u062a \u062d\u0627\u0641\u0638\u0647 \u0627\u0636\u0627\u0641\u0647 \u0646\u0645\u06cc\u200c\u06af\u06cc\u0631\u0646\u062f.<\/p>\n\n\n\n

\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc O(q\\times lg(N_q)) <\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

\u062e\u0628 \u0628\u062f\u0648\u0646 \u0645\u0642\u062f\u0645\u0647 \u0645\u06cc\u0631\u06cc\u0645 \u0633\u0631\u0627\u063a \u0633\u0648\u0627\u0644 \u0647\u0627 : \u0633\u0648\u0627\u0644 \u0646\u0641\u0633\u200c\u06af\u06cc\u0631:\u200c \u0628\u0631\u0627\u06cc \u0633\u0648\u0627\u0644 \u0627\u0645 \u060c \u0628\u0627\u0631 \u0646\u0641\u0633 \u0647\u0627 \u06af\u0631\u0641\u062a\u0647 \u0645\u06cc \u0634\u0648\u062f….<\/p>\n","protected":false},"author":6,"featured_media":32293,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46,50,141],"tags":[],"class_list":["post-3404","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-developer","category-quera-developer","category-contests-and-events"],"yoast_head":"\n\u067e\u0627\u0633\u062e \u0633\u0648\u0627\u0644\u0627\u062a \u0645\u0633\u0627\u0628\u0642\u0647 \u06f2\u06f6 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u06cc - \u06a9\u0648\u0626\u0631\u0627\u200c\u0628\u0644\u0627\u06af<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/quera.org\/blog\/\u067e\u0627\u0633\u062e-\u0633\u0648\u0627\u0644\u0627\u062a-\u0645\u0633\u0627\u0628\u0642\u0647-\u06f2\u06f6-\u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u06cc\/\" \/>\n<meta property=\"og:locale\" content=\"fa_IR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"\u067e\u0627\u0633\u062e \u0633\u0648\u0627\u0644\u0627\u062a \u0645\u0633\u0627\u0628\u0642\u0647 \u06f2\u06f6 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u06cc - \u06a9\u0648\u0626\u0631\u0627\u200c\u0628\u0644\u0627\u06af\" \/>\n<meta property=\"og:description\" content=\"\u062e\u0628 \u0628\u062f\u0648\u0646 \u0645\u0642\u062f\u0645\u0647 \u0645\u06cc\u0631\u06cc\u0645 \u0633\u0631\u0627\u063a \u0633\u0648\u0627\u0644 \u0647\u0627 : \u0633\u0648\u0627\u0644 \u0646\u0641\u0633\u200c\u06af\u06cc\u0631:\u200c \u0628\u0631\u0627\u06cc \u0633\u0648\u0627\u0644 \u0627\u0645 \u060c \u0628\u0627\u0631 \u0646\u0641\u0633 \u0647\u0627 \u06af\u0631\u0641\u062a\u0647 \u0645\u06cc \u0634\u0648\u062f....\" \/>\n<meta property=\"og:url\" content=\"https:\/\/quera.org\/blog\/\u067e\u0627\u0633\u062e-\u0633\u0648\u0627\u0644\u0627\u062a-\u0645\u0633\u0627\u0628\u0642\u0647-\u06f2\u06f6-\u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u06cc\/\" \/>\n<meta property=\"og:site_name\" content=\"\u06a9\u0648\u0626\u0631\u0627\u200c\u0628\u0644\u0627\u06af\" \/>\n<meta property=\"article:published_time\" content=\"2019-03-30T17:48:08+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2022-01-06T07:08:39+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/quera.org\/blog\/wp-content\/uploads\/2019\/03\/solution.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1000\" \/>\n\t<meta property=\"og:image:height\" content=\"707\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"\u06a9\u0648\u0626\u0631\u0627 \u0628\u0644\u0627\u06af\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u0646\u0648\u0634\u062a\u0647\u200c\u0634\u062f\u0647 \u0628\u062f\u0633\u062a\" \/>\n\t<meta name=\"twitter:data1\" content=\"\u06a9\u0648\u0626\u0631\u0627 \u0628\u0644\u0627\u06af\" \/>\n\t<meta name=\"twitter:label2\" content=\"\u0632\u0645\u0627\u0646 \u062a\u0642\u0631\u06cc\u0628\u06cc \u0628\u0631\u0627\u06cc \u062e\u0648\u0627\u0646\u062f\u0646\" \/>\n\t<meta name=\"twitter:data2\" content=\"13 \u062f\u0642\u06cc\u0642\u0647\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"TechArticle\",\"@id\":\"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/\"},\"author\":{\"name\":\"\u06a9\u0648\u0626\u0631\u0627 \u0628\u0644\u0627\u06af\",\"@id\":\"https:\/\/quera.org\/blog\/#\/schema\/person\/256c0fa1a4179442163f152ffeb1006d\"},\"headline\":\"\u067e\u0627\u0633\u062e \u0633\u0648\u0627\u0644\u0627\u062a \u0645\u0633\u0627\u0628\u0642\u0647 \u06f2\u06f6 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u06cc\",\"datePublished\":\"2019-03-30T17:48:08+00:00\",\"dateModified\":\"2022-01-06T07:08:39+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/\"},\"wordCount\":859,\"commentCount\":1,\"publisher\":{\"@id\":\"https:\/\/quera.org\/blog\/#organization\"},\"image\":{\"@id\":\"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/quera.org\/blog\/wp-content\/uploads\/2019\/03\/solution.jpg\",\"articleSection\":[\"\u062a\u0648\u0633\u0639\u0647\u200c\u062f\u0647\u0646\u062f\u0647\",\"\u0628\u0627 \u06a9\u0648\u0626\u0631\u0627 | \u062a\u0648\u0633\u0639\u0647\u200c\u062f\u0647\u0646\u062f\u0647\",\"\u0645\u0633\u0627\u0628\u0642\u0627\u062a \u0648 \u0631\u0648\u06cc\u062f\u0627\u062f\u0647\u0627\"],\"inLanguage\":\"fa-IR\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/\",\"url\":\"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/\",\"name\":\"\u067e\u0627\u0633\u062e \u0633\u0648\u0627\u0644\u0627\u062a \u0645\u0633\u0627\u0628\u0642\u0647 \u06f2\u06f6 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u06cc - \u06a9\u0648\u0626\u0631\u0627\u200c\u0628\u0644\u0627\u06af\",\"isPartOf\":{\"@id\":\"https:\/\/quera.org\/blog\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/quera.org\/blog\/wp-content\/uploads\/2019\/03\/solution.jpg\",\"datePublished\":\"2019-03-30T17:48:08+00:00\",\"dateModified\":\"2022-01-06T07:08:39+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/#breadcrumb\"},\"inLanguage\":\"fa-IR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"fa-IR\",\"@id\":\"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/#primaryimage\",\"url\":\"https:\/\/quera.org\/blog\/wp-content\/uploads\/2019\/03\/solution.jpg\",\"contentUrl\":\"https:\/\/quera.org\/blog\/wp-content\/uploads\/2019\/03\/solution.jpg\",\"width\":1000,\"height\":707},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\u062e\u0627\u0646\u0647\",\"item\":\"https:\/\/quera.org\/blog\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"\u062a\u0648\u0633\u0639\u0647\u200c\u062f\u0647\u0646\u062f\u0647\",\"item\":\"https:\/\/quera.org\/blog\/category\/developer\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"\u0628\u0627 \u06a9\u0648\u0626\u0631\u0627 | \u062a\u0648\u0633\u0639\u0647\u200c\u062f\u0647\u0646\u062f\u0647\",\"item\":\"https:\/\/quera.org\/blog\/category\/developer\/quera-developer\/\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"\u0645\u0633\u0627\u0628\u0642\u0627\u062a \u0648 \u0631\u0648\u06cc\u062f\u0627\u062f\u0647\u0627\",\"item\":\"https:\/\/quera.org\/blog\/category\/developer\/quera-developer\/contests-and-events\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"\u067e\u0627\u0633\u062e \u0633\u0648\u0627\u0644\u0627\u062a \u0645\u0633\u0627\u0628\u0642\u0647 \u06f2\u06f6 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u06cc\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/quera.org\/blog\/#website\",\"url\":\"https:\/\/quera.org\/blog\/\",\"name\":\"\u06a9\u0648\u0626\u0631\u0627\u200c\u0628\u0644\u0627\u06af\",\"description\":\"\u0647\u0645\u0647\u200c\u0686\u06cc\u0632 \u062f\u0631\u0628\u0627\u0631\u0647 \u062f\u0646\u06cc\u0627\u06cc \u0628\u0631\u0646\u0627\u0645\u0647\u200c\u0646\u0648\u06cc\u0633\u06cc\",\"publisher\":{\"@id\":\"https:\/\/quera.org\/blog\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/quera.org\/blog\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"fa-IR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/quera.org\/blog\/#organization\",\"name\":\"\u06a9\u0648\u0626\u0631\u0627\",\"url\":\"https:\/\/quera.org\/blog\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"fa-IR\",\"@id\":\"https:\/\/quera.org\/blog\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/quera.org\/blog\/wp-content\/uploads\/2022\/09\/logo-quera22-e1574766184574.png\",\"contentUrl\":\"https:\/\/quera.org\/blog\/wp-content\/uploads\/2022\/09\/logo-quera22-e1574766184574.png\",\"width\":300,\"height\":300,\"caption\":\"\u06a9\u0648\u0626\u0631\u0627\"},\"image\":{\"@id\":\"https:\/\/quera.org\/blog\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/www.instagram.com\/quera.ir\/\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/quera.org\/blog\/#\/schema\/person\/256c0fa1a4179442163f152ffeb1006d\",\"name\":\"\u06a9\u0648\u0626\u0631\u0627 \u0628\u0644\u0627\u06af\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"fa-IR\",\"@id\":\"https:\/\/quera.org\/blog\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/cfb7f309160ff094521c9031a472e80ecb7d1ee5380f9931aee8489aa6b4abb2?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/cfb7f309160ff094521c9031a472e80ecb7d1ee5380f9931aee8489aa6b4abb2?s=96&d=mm&r=g\",\"caption\":\"\u06a9\u0648\u0626\u0631\u0627 \u0628\u0644\u0627\u06af\"}}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"\u067e\u0627\u0633\u062e \u0633\u0648\u0627\u0644\u0627\u062a \u0645\u0633\u0627\u0628\u0642\u0647 \u06f2\u06f6 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u06cc - \u06a9\u0648\u0626\u0631\u0627\u200c\u0628\u0644\u0627\u06af","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/quera.org\/blog\/\u067e\u0627\u0633\u062e-\u0633\u0648\u0627\u0644\u0627\u062a-\u0645\u0633\u0627\u0628\u0642\u0647-\u06f2\u06f6-\u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u06cc\/","og_locale":"fa_IR","og_type":"article","og_title":"\u067e\u0627\u0633\u062e \u0633\u0648\u0627\u0644\u0627\u062a \u0645\u0633\u0627\u0628\u0642\u0647 \u06f2\u06f6 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u06cc - \u06a9\u0648\u0626\u0631\u0627\u200c\u0628\u0644\u0627\u06af","og_description":"\u062e\u0628 \u0628\u062f\u0648\u0646 \u0645\u0642\u062f\u0645\u0647 \u0645\u06cc\u0631\u06cc\u0645 \u0633\u0631\u0627\u063a \u0633\u0648\u0627\u0644 \u0647\u0627 : \u0633\u0648\u0627\u0644 \u0646\u0641\u0633\u200c\u06af\u06cc\u0631:\u200c \u0628\u0631\u0627\u06cc \u0633\u0648\u0627\u0644 \u0627\u0645 \u060c \u0628\u0627\u0631 \u0646\u0641\u0633 \u0647\u0627 \u06af\u0631\u0641\u062a\u0647 \u0645\u06cc \u0634\u0648\u062f....","og_url":"https:\/\/quera.org\/blog\/\u067e\u0627\u0633\u062e-\u0633\u0648\u0627\u0644\u0627\u062a-\u0645\u0633\u0627\u0628\u0642\u0647-\u06f2\u06f6-\u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u06cc\/","og_site_name":"\u06a9\u0648\u0626\u0631\u0627\u200c\u0628\u0644\u0627\u06af","article_published_time":"2019-03-30T17:48:08+00:00","article_modified_time":"2022-01-06T07:08:39+00:00","og_image":[{"width":1000,"height":707,"url":"https:\/\/quera.org\/blog\/wp-content\/uploads\/2019\/03\/solution.jpg","type":"image\/jpeg"}],"author":"\u06a9\u0648\u0626\u0631\u0627 \u0628\u0644\u0627\u06af","twitter_card":"summary_large_image","twitter_misc":{"\u0646\u0648\u0634\u062a\u0647\u200c\u0634\u062f\u0647 \u0628\u062f\u0633\u062a":"\u06a9\u0648\u0626\u0631\u0627 \u0628\u0644\u0627\u06af","\u0632\u0645\u0627\u0646 \u062a\u0642\u0631\u06cc\u0628\u06cc \u0628\u0631\u0627\u06cc \u062e\u0648\u0627\u0646\u062f\u0646":"13 \u062f\u0642\u06cc\u0642\u0647"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"TechArticle","@id":"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/#article","isPartOf":{"@id":"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/"},"author":{"name":"\u06a9\u0648\u0626\u0631\u0627 \u0628\u0644\u0627\u06af","@id":"https:\/\/quera.org\/blog\/#\/schema\/person\/256c0fa1a4179442163f152ffeb1006d"},"headline":"\u067e\u0627\u0633\u062e \u0633\u0648\u0627\u0644\u0627\u062a \u0645\u0633\u0627\u0628\u0642\u0647 \u06f2\u06f6 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u06cc","datePublished":"2019-03-30T17:48:08+00:00","dateModified":"2022-01-06T07:08:39+00:00","mainEntityOfPage":{"@id":"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/"},"wordCount":859,"commentCount":1,"publisher":{"@id":"https:\/\/quera.org\/blog\/#organization"},"image":{"@id":"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/#primaryimage"},"thumbnailUrl":"https:\/\/quera.org\/blog\/wp-content\/uploads\/2019\/03\/solution.jpg","articleSection":["\u062a\u0648\u0633\u0639\u0647\u200c\u062f\u0647\u0646\u062f\u0647","\u0628\u0627 \u06a9\u0648\u0626\u0631\u0627 | \u062a\u0648\u0633\u0639\u0647\u200c\u062f\u0647\u0646\u062f\u0647","\u0645\u0633\u0627\u0628\u0642\u0627\u062a \u0648 \u0631\u0648\u06cc\u062f\u0627\u062f\u0647\u0627"],"inLanguage":"fa-IR","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/","url":"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/","name":"\u067e\u0627\u0633\u062e \u0633\u0648\u0627\u0644\u0627\u062a \u0645\u0633\u0627\u0628\u0642\u0647 \u06f2\u06f6 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u06cc - \u06a9\u0648\u0626\u0631\u0627\u200c\u0628\u0644\u0627\u06af","isPartOf":{"@id":"https:\/\/quera.org\/blog\/#website"},"primaryImageOfPage":{"@id":"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/#primaryimage"},"image":{"@id":"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/#primaryimage"},"thumbnailUrl":"https:\/\/quera.org\/blog\/wp-content\/uploads\/2019\/03\/solution.jpg","datePublished":"2019-03-30T17:48:08+00:00","dateModified":"2022-01-06T07:08:39+00:00","breadcrumb":{"@id":"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/#breadcrumb"},"inLanguage":"fa-IR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/"]}]},{"@type":"ImageObject","inLanguage":"fa-IR","@id":"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/#primaryimage","url":"https:\/\/quera.org\/blog\/wp-content\/uploads\/2019\/03\/solution.jpg","contentUrl":"https:\/\/quera.org\/blog\/wp-content\/uploads\/2019\/03\/solution.jpg","width":1000,"height":707},{"@type":"BreadcrumbList","@id":"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\u062e\u0627\u0646\u0647","item":"https:\/\/quera.org\/blog\/"},{"@type":"ListItem","position":2,"name":"\u062a\u0648\u0633\u0639\u0647\u200c\u062f\u0647\u0646\u062f\u0647","item":"https:\/\/quera.org\/blog\/category\/developer\/"},{"@type":"ListItem","position":3,"name":"\u0628\u0627 \u06a9\u0648\u0626\u0631\u0627 | \u062a\u0648\u0633\u0639\u0647\u200c\u062f\u0647\u0646\u062f\u0647","item":"https:\/\/quera.org\/blog\/category\/developer\/quera-developer\/"},{"@type":"ListItem","position":4,"name":"\u0645\u0633\u0627\u0628\u0642\u0627\u062a \u0648 \u0631\u0648\u06cc\u062f\u0627\u062f\u0647\u0627","item":"https:\/\/quera.org\/blog\/category\/developer\/quera-developer\/contests-and-events\/"},{"@type":"ListItem","position":5,"name":"\u067e\u0627\u0633\u062e \u0633\u0648\u0627\u0644\u0627\u062a \u0645\u0633\u0627\u0628\u0642\u0647 \u06f2\u06f6 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u06cc"}]},{"@type":"WebSite","@id":"https:\/\/quera.org\/blog\/#website","url":"https:\/\/quera.org\/blog\/","name":"\u06a9\u0648\u0626\u0631\u0627\u200c\u0628\u0644\u0627\u06af","description":"\u0647\u0645\u0647\u200c\u0686\u06cc\u0632 \u062f\u0631\u0628\u0627\u0631\u0647 \u062f\u0646\u06cc\u0627\u06cc \u0628\u0631\u0646\u0627\u0645\u0647\u200c\u0646\u0648\u06cc\u0633\u06cc","publisher":{"@id":"https:\/\/quera.org\/blog\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/quera.org\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"fa-IR"},{"@type":"Organization","@id":"https:\/\/quera.org\/blog\/#organization","name":"\u06a9\u0648\u0626\u0631\u0627","url":"https:\/\/quera.org\/blog\/","logo":{"@type":"ImageObject","inLanguage":"fa-IR","@id":"https:\/\/quera.org\/blog\/#\/schema\/logo\/image\/","url":"https:\/\/quera.org\/blog\/wp-content\/uploads\/2022\/09\/logo-quera22-e1574766184574.png","contentUrl":"https:\/\/quera.org\/blog\/wp-content\/uploads\/2022\/09\/logo-quera22-e1574766184574.png","width":300,"height":300,"caption":"\u06a9\u0648\u0626\u0631\u0627"},"image":{"@id":"https:\/\/quera.org\/blog\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.instagram.com\/quera.ir\/"]},{"@type":"Person","@id":"https:\/\/quera.org\/blog\/#\/schema\/person\/256c0fa1a4179442163f152ffeb1006d","name":"\u06a9\u0648\u0626\u0631\u0627 \u0628\u0644\u0627\u06af","image":{"@type":"ImageObject","inLanguage":"fa-IR","@id":"https:\/\/quera.org\/blog\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/cfb7f309160ff094521c9031a472e80ecb7d1ee5380f9931aee8489aa6b4abb2?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/cfb7f309160ff094521c9031a472e80ecb7d1ee5380f9931aee8489aa6b4abb2?s=96&d=mm&r=g","caption":"\u06a9\u0648\u0626\u0631\u0627 \u0628\u0644\u0627\u06af"}}]}},"_links":{"self":[{"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/posts\/3404","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/users\/6"}],"replies":[{"embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/comments?post=3404"}],"version-history":[{"count":1,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/posts\/3404\/revisions"}],"predecessor-version":[{"id":32294,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/posts\/3404\/revisions\/32294"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/media\/32293"}],"wp:attachment":[{"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/media?parent=3404"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/categories?post=3404"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/tags?post=3404"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}