{"id":1357,"date":"2020-06-20T12:14:56","date_gmt":"2020-06-20T19:14:56","guid":{"rendered":"http:\/\/209.126.2.187\/?p=1357"},"modified":"2020-06-20T12:15:03","modified_gmt":"2020-06-20T19:15:03","slug":"modular-multiplicative-inverse-concepts","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/06\/20\/modular-multiplicative-inverse-concepts\/","title":{"rendered":"Modular Multiplicative Inverse Concepts"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">Summary<\/h2>\n\n\n\n<p>Given a modular <code>MOD<\/code>, if we want to calculate the division of two integers, we could use the technique Modular Multiplicative Inverse.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\">a \/ b = a * b_ % MOD => b * b_ % mod = 1<\/code><\/pre>\n\n\n\n<p>To calculate <code>b_<\/code>, we could use <a href=\"https:\/\/en.wikipedia.org\/wiki\/Fermat%27s_little_theorem\">Fermat&#8217;s little theorem<\/a>. If<em> <\/em><code>mod<\/code>\u00a0is a\u00a0prime number, we have<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\">b^mod % mod = b => b^(mod-1) % mod = 1 => b^(mod-1) = b * b_ => b_ = b^(mod-2) % mod<\/code><\/pre>\n\n\n\n<p>If we use Binary Exponentiation technique, we could calculate <code>b_<\/code> efficiently. <\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">auto b_ = power(b, mod - 2, mod);\nll power(ll base, int i, int mod) {\n      if (i == 0) {\n          return 1;\n      } else if (i == 1) {\n          return base;\n      } else if ((i &amp; 1) == 0) {\n          return power((base * base) % mod, i \/ 2, mod);\n      } else {\n          return (base * power((base * base) % mod, (i - 1) \/ 2, mod)) % mod;\n      }\n  }<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Summary Given a modular MOD, if we want to calculate the division of two integers, we could use the technique Modular Multiplicative Inverse. To calculate b_, we could use Fermat&#8217;s little theorem. If mod\u00a0is a\u00a0prime number, we have If we use Binary Exponentiation technique, we could calculate b_ efficiently.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-1357","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1357","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=1357"}],"version-history":[{"count":3,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1357\/revisions"}],"predecessor-version":[{"id":1360,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1357\/revisions\/1360"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1357"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1357"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1357"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}