{"id":1595,"date":"2021-06-30T21:43:50","date_gmt":"2021-07-01T04:43:50","guid":{"rendered":"http:\/\/66.94.114.210\/?p=1595"},"modified":"2021-06-30T22:13:45","modified_gmt":"2021-07-01T05:13:45","slug":"modular-multiplicative-inverse","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2021\/06\/30\/modular-multiplicative-inverse\/","title":{"rendered":"Modular Multiplicative Inverse"},"content":{"rendered":"\n<p>If we have <code>a * x = 1 (mod kMod)<\/code>, we call <code>x<\/code> is a multiplicative inverse of <code>a<\/code> when modular is <code>kMod<\/code> (in this post, <code>kMod<\/code> is a prime number). Usually we use <code>a^-1<\/code> to represent it.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Binary Exponentiation<\/h2>\n\n\n\n<p>Given a and <code>kMod<\/code>, we can get <code>a^-1<\/code> in <code>O(logkMod)<\/code> time.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">\/\/ a * x == 1 (mod kMod)\n\/\/ according to Fermat's little theorem (https:\/\/en.wikipedia.org\/wiki\/Fermat%27s_little_theorem)\n\/\/ we have a * x == a^(kMod-1)\n\/\/ so x == a^(kMod-2)\n\nll GetInverse(int val) { return FastPower(val, kMod - 2); }\nll FastPower(ll val, unsigned int n) {\n  if (n == 0) {\n    return 1;\n  }\n  if (n == 1) {\n    return val;\n  }\n  if (n % 2 == 0) {\n    return FastPower((val * val) % kMod, n \/ 2);\n  }\n  return (FastPower((val * val) % kMod, (n - 1) \/ 2) * val) % kMod;\n}<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"> Dynamic Programming<\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">int GetInverse(int n) {\n  inv[1] = 1;\n  for (int i = 2; i &lt;= n; ++i) {\n    inv[i] = (ll)(kMod - kMod \/ i) * inv[kMod % i] % p;\n  }\n}<\/code><\/pre>\n\n\n\n<p>This solves inverse of <code>[1, n]<\/code> in linear time. See <a href=\"https:\/\/oi-wiki.org\/math\/inverse\/#_5\">https:\/\/oi-wiki.org\/math\/inverse\/#_5<\/a> for details.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">prefix_mul[0] = 1;\nfor (int i = 1; i &lt;= n; ++i) {\n  prefix_mul[i] = prefix_mul[i - 1] * nums[i] % kMod;\n}\nprefix_mul_inverse[n] = GetInverse(prefix_mul[n], kMod - 2);\nfor (int i = n; i >= 1; --i) {\n  \/\/ prefix_mul_inverse[i] = nums[0]^-1 * ... * nums[i]^-1\n  \/\/ so prefix_mul_inverse[i] * nums[i] = nums[0]^-1 * ... * nums[i - 1]^-1\n  prefix_mul_inverse[i - 1] = prefix_mul_inverse[i] * nums[i] % kMod;\n}\nfor (int i = 1; i &lt;= n; ++i) {\n  \/\/ prefix_mul_inverse[i] = nums[0]^-1 * ... * nums[i]^-1\n  \/\/ prefix_mul[i - 1] = nums[0] * ... * nums[i - 1]\n  nums_inverse[i] = prefix_mul_inverse[i] * prefix_mul[i - 1] % kMod;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>If we have a * x = 1 (mod kMod), we call x is a multiplicative inverse of a when modular is kMod (in this post, kMod is a prime number). Usually we use a^-1 to represent it. Binary Exponentiation Given a and kMod, we can get a^-1 in O(logkMod) time. Dynamic Programming This solves&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,49],"tags":[],"class_list":["post-1595","post","type-post","status-publish","format-standard","hentry","category-alg","category-math"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1595","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=1595"}],"version-history":[{"count":6,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1595\/revisions"}],"predecessor-version":[{"id":1608,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1595\/revisions\/1608"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1595"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1595"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1595"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}