{"id":965,"date":"2014-09-09T02:52:30","date_gmt":"2014-09-08T18:52:30","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=965"},"modified":"2014-09-14T01:23:04","modified_gmt":"2014-09-13T17:23:04","slug":"bzoj-2219-%e6%95%b0%e8%ae%ba%e4%b9%8b%e7%a5%9e","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/bzoj-2219-%e6%95%b0%e8%ae%ba%e4%b9%8b%e7%a5%9e\/","title":{"rendered":"BZOJ 2219: \u6570\u8bba\u4e4b\u795e"},"content":{"rendered":"<p><!--more--><br \/>\n<a href=\"http:\/\/www.lydsy.com\/JudgeOnline\/problem.php?id=2219\">http:\/\/www.lydsy.com\/JudgeOnline\/problem.php?id=2219<\/a><br \/>\n<a href=\"http:\/\/jcvb.is-programmer.com\/posts\/42036\">http:\/\/jcvb.is-programmer.com\/posts\/42036<\/a><\/p>\n<p>\u8003\u5bdf\u540c\u4f59\u65b9\u7a0b&#8230;<br \/>\na^x = b (mod p)<br \/>\n\u5df2\u77e5 x,b \u65f6\uff0c\u6c42 a\u3002<\/p>\n<p>\u2014\u2014<br \/>\n\u9996\u5148 CRT \u3002\u3002\u3002\uff08\u4fdd\u8bc1 p \u6709\u539f\u6839\u53ef\u4ee5\u53d6\u6307\u6807\uff0c\u53d6\u6307\u6807\u5927\u6982\u53ef\u4ee5\u7c7b\u6bd4\u79bb\u6563\u5bf9\u6570\u3002\u3002\uff09<\/p>\n<p>x ind a = ind b ( mod p)<\/p>\n<p>\u6c42\u51fa\u539f\u6839 g\u3002\u3002(\u4f3c\u4e4e\u53ea\u80fd\u66b4\u529b\uff1f<br \/>\n\u7136\u540e\u7528 exDlog \u6c42\u51fa ind b\u3002\u3002\u3002<br \/>\n\u4e8e\u662f\u5c31\u8f6c\u6362\u6210\u4e86\u7ebf\u6027\u540c\u4f59\u65b9\u7a0b\u95ee\u9898\u3002\u3002<\/p>\n<p><a href=\"https:\/\/gist.github.com\/lychees\/86926b622aac855acfb4\">https:\/\/gist.github.com\/lychees\/86926b622aac855acfb4<\/a><\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\nint getPrimitive(int p){\r\n    --p; VI d; for (int i=2;i*i&lt;=p;++i) if (!(p%i)) d.PB(i), d.PB(p\/i);\r\n    UNQ(d); MOD = ++p; FOR(i, 2, p){\r\n        int j = 0; REP_N(j, SZ(d)) if (pow(i, d&#x5B;j]) == 1) break;\r\n        if (j == SZ(d)) return i;\r\n    }\r\n    assert(0);\r\n    return -1; \/\/!\r\n}\r\n\r\nint f(int x, int b, PII p){\r\n    int pp = poww(p.fi, p.se); b %= pp; if (!b) return poww(p.fi, p.se - ceil(p.se, x));\r\n    int phi = pp-pp\/p.fi, g=getPrimitive(p.fi);\r\n    MOD = pp; int bb = Dlog(g, b), d = gcd(x, phi);\r\n    return bb%d?0:d;\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n    \/\/freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n    sieve(); Rush{\r\n        int x, b, p; RD(x, b, p); p&lt;&lt;=1, ++p; fact(p);\r\n        int res = 1; ECH(it, fac) res *= f(x, b, *it);\r\n        OT(res);\r\n    }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-965","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-fz","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/965","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=965"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/965\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=965"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=965"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=965"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}