{"id":64,"date":"2011-03-30T07:39:14","date_gmt":"2011-03-29T23:39:14","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=64"},"modified":"2012-03-03T07:44:41","modified_gmt":"2012-03-02T23:44:41","slug":"spoj-3105-power-modulo-inverted","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/spoj-3105-power-modulo-inverted\/","title":{"rendered":"SPOJ 3105. Power Modulo Inverted"},"content":{"rendered":"<h3>Brief description :<\/h3>\n<p>&#8230;<\/p>\n<p><!--more--><\/p>\n<h3>Analyse :<\/h3>\n<p>&#8230;<\/p>\n<pre lang=\"cpp\">\r\n#include <iostream>\r\n#include <cstdio>\r\n#include <cmath>\r\n\r\nusing namespace std;\r\nconst int N = 1000;\r\nconst int MaxH = 1000;\r\nint A[N];\r\nint a, b, p;\r\n\r\n\r\n\r\nstruct HashTable{\r\n\tint index[MaxH], head[MaxH], next[MaxH], sz;\r\n\tint key[MaxH];\r\n\t\r\n\tinline void clear() {\r\n\t\tsz = 0;\r\n\t\tmemset(head, -1, sizeof(head));\r\n\t}\r\n\tinline void insert(int id, int val) {\r\n\t\tint x = id % MaxH;\r\n\t\tindex[sz] = id, key[sz] = val;\r\n\t\tnext[sz] = head[x];\r\n\t\thead[x] = sz++;\r\n\t}\r\n\tinline int search(int id){\r\n\t\tint x = id % MaxH;\r\n\t\tfor ( int it = head[x] ; it != -1 ; it = next[it] ) \r\n\t\t\tif ( index[it] == id ) return key[it];\r\n\t\treturn -1;\r\n\t}\r\n} hash;\r\n\r\n\r\n\r\ninline int _M(int a){\r\n\tif (a < 0) return a + p;\r\n\treturn a;\r\n}\r\n\r\ninline int _I(int b){\r\n\tint a = p;\r\n\tint x1 = 0, x2 = 1, q;\r\n\twhile (true){\r\n\t\tq = a \/ b, a %= b;\r\n\t\tif (!a) return _M(x2);\r\n\t\tx1 -= q * x2;\r\n\t\tq = b \/ a, b %= a;\r\n\t\tif (!b) return _M(x1);\r\n\t\tx2 -= q * x1;\r\n\t}\r\n}\r\n\r\nint Dlog(){\r\n\r\n\t\/\/ Baby-Step ...\r\n\tint m = ceil(sqrt(p)); \/\/??\r\n\t\r\n\tA[0] = 1;\r\n\tfor (int i=1;i<=m;i++){\r\n\t\tA[i] = (A[i-1] * a) % p;\r\n\t\tif (A[i] == b) return i;\r\n\t}\r\n\t\r\n\thash.clear();\r\n\tfor (int i=0;i<m;i++)\r\n\t\thash.insert(i, A[i]);\r\n\t\r\n\t\r\n\t\/\/ Giant-Step ...\r\n\tint I0 = _I(a), I;\r\n\tfor (int i=1;i<m;i++){\r\n\t\tint j = hash.search(I);\r\n\t\tif (j!=-1) return i*m + j;\r\n\t\telse I = (I * I0) % p;\r\n\t}\r\n\treturn -1;\r\n}\r\n\r\n\r\n\r\nint main(){\r\n\twhile (cin >> a >> b >> p){\r\n\t\tcout << Dlog() << endl;\r\n\t}\r\n}\r\n\r\n\/*\r\n p \u7d20\u6570. ..\r\n \r\n a, p \u4e92\u7d20\r\n\r\n a, p \u4e0d\u4e92\u7d20\r\n*\/\r\n<\/pre>\n<p><bk><bk><\/p>\n<h3>External link :<\/h3>\n<ol>\n<a href=\"https:\/\/www.spoj.pl\/problems\/MOD\/\">https:\/\/www.spoj.pl\/problems\/MOD\/<\/a><\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Brief description : &#8230;<\/p>\n","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":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[21],"tags":[],"class_list":["post-64","post","type-post","status-publish","format-standard","hentry","category-spoj"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-12","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/64","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=64"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/64\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=64"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=64"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=64"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}