blocks|key|5114812|text|Python，29字节|type|header-two|depth|inlineStyleRanges|entityRanges|data|5114813|lambda+x,n:pow(x,2**n-1,2**n)|code-block|syntax|javascript|5114814|它使用欧拉定理，观察到2%5En−1可以被2%5E(n−1)−1除以2%5E(n−1)−1。这是足够快的n到7000左右，在那里它开始花费超过一秒钟。|unstyled|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|I|7|M|8|@]|9|@]|A|$]]]|J|$]]

<h1>Python, 29 bytes</h1>

<pre class="lang-py prettyprint-override"><code>lambda x,n:pow(x,2**n-1,2**n)
</code></pre>

<p>This returns 0 for even <em>x</em>. It uses Euler’s theorem, with the observation that 2^<em>n</em> − 1 is divisible by 2^(<em>n</em> − 1) − 1, via Python’s builtin fast modular exponentiation. This is plenty fast enough for <em>n</em> up to 7000 or so, where it starts taking more than about a second.</p>


blocks|key|6303161|text|Python3.8+(预发行版)，25字节|type|header-two|depth|inlineStyleRanges|entityRanges|offset|length|data|6303162|lambda+a,b:pow(a,-1,2**b)|code-block|syntax|javascript|6303163|在网上试试！|unstyled|entityMap|0|LINK|mutability|MUTABLE|url|https://docs.python.org/3.8/|1|https://tio.run/##XY3PCsIwDMbvfYqwUzfq2CaiDDz6Cp68tK7DQteWNP7Z09duigc/SAhffl8SZrp5tz0ETCMc4ZKsnNQgQQrVB//kUmxa0VWVKpOZgkeCOEfGRo9gjdNg3GLUkQbjegZZhPNnWCQFqHx2koEbR2LN1DFYQ7wsf1TAvOQjX@ivrV9XHQjO0t71CdFj/0cXzlP@/tBIRlldlKltYMf2a3UN2ze5vwE^0|0|G|0|0|0|0|6|1^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@$A|V|B|W|1|X]]|C|$]]|$1|D|3|E|5|F|7|Y|8|@]|9|@]|C|$G|H]]|$1|I|3|J|5|K|7|Z|8|@]|9|@$A|10|B|11|1|12]]|C|$]]]|L|$M|$5|N|O|P|C|$Q|R]]|S|$5|N|O|P|C|$Q|T]]]]

<h1><a href="https://docs.python.org/3.8/" rel="nofollow noreferrer">Python 3.8 (pre-release)</a>, 25 bytes</h1>



<pre class="lang-python prettyprint-override"><code>lambda a,b:pow(a,-1,2**b)
</code></pre>

<p><a href="https://tio.run/##XY3PCsIwDMbvfYqwUzfq2CaiDDz6Cp68tK7DQteWNP7Z09duigc/SAhffl8SZrp5tz0ETCMc4ZKsnNQgQQrVB//kUmxa0VWVKpOZgkeCOEfGRo9gjdNg3GLUkQbjegZZhPNnWCQFqHx2koEbR2LN1DFYQ7wsf1TAvOQjX@ivrV9XHQjO0t71CdFj/0cXzlP@/tBIRlldlKltYMf2a3UN2ze5vwE" rel="nofollow noreferrer" title="Python 3.8 (pre-release) – Try It Online">Try it online!</a></p>


blocks|key|5114737|text|Mathatica-22|type|header-two|depth|inlineStyleRanges|entityRanges|data|5114738|f=PowerMod[#,-1,2%5E#2]&|code-block|syntax|javascript|5114739|f[x,n]与x*y=1+mod+2%5En一起返回y，否则返回x+is+not+invertible+modulo+2%5En|unstyled|offset|length|style|CODE|entityMap^0|0|0|0|6|7|D|O|1|U|U^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|I|7|Q|8|@$J|R|K|S|L|M]|$J|T|K|U|L|M]|$J|V|K|W|L|M]|$J|X|K|Y|L|M]]|9|@]|A|$]]]|N|$]]

<h2>Mathematica - 22</h2>
<pre><code>f=PowerMod[#,-1,2^#2]&amp;
</code></pre>
<p><code>f[x,n]</code> returns <code>y</code> with <code>x*y=1 mod 2^n</code>, otherwise <code>x is not invertible modulo 2^n</code></p>


blocks|key|6302569|text|Ruby-88个字符|type|header-two|depth|inlineStyleRanges|entityRanges|data|6302570|使用函数f。|unstyled|offset|length|style|CODE|6302571|def+e+a,b;a%25b==0?[0,1]:(x,y=e(b,a%25b);[y,x-(y*(a/b))])end
def+f+x,n;e(x,2**n)[0]*(x%252)end|code-block|syntax|javascript|6302572|只需从链接的wiki页面返回递归函数，就会在出错时返回0。|entityMap^0|0|4|1|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|R|8|@$E|S|F|T|G|H]]|9|@]|A|$]]|$1|I|3|J|5|K|7|U|8|@]|9|@]|A|$L|M]]|$1|N|3|O|5|D|7|V|8|@]|9|@]|A|$]]]|P|$]]

<h2>Ruby - 88 characters</h2>

<p>Use the function <code>f</code>.</p>

<pre><code>def e a,b;a%b==0?[0,1]:(x,y=e(b,a%b);[y,x-(y*(a/b))])end
def f x,n;e(x,2**n)[0]*(x%2)end
</code></pre>

<p>Simply the recursive function from the linked wiki page, returns 0 on error.</p>


blocks|key|6303101|text|Haskell，42字节|type|header-two|depth|inlineStyleRanges|entityRanges|data|6303102|_!1=1
x!n%7Cr<-x!div(n%2B1)2=(2-r*x)*r`mod`2%5En|code-block|syntax|javascript|6303103|使用基于Hensel引理的算法将每次迭代中的数字数增加一倍，这将在1秒钟内运行，最多可达3000万！|unstyled|offset|length|entityMap|0|LINK|mutability|MUTABLE|url|http://arxiv.org/abs/1209.6626^0|0|0|2|D|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|I|7|U|8|@]|9|@$J|V|K|W|1|X]]|A|$]]]|L|$M|$5|N|O|P|A|$Q|R]]]]

<h1>Haskell, 42 bytes</h1>

<pre class="lang-hs prettyprint-override"><code>_!1=1
x!n|r&lt;-x!div(n+1)2=(2-r*x)*r`mod`2^n
</code></pre>

<p>Using an <a href="http://arxiv.org/abs/1209.6626" rel="nofollow">algorithm based on Hensel’s lemma</a> that doubles the number of digits in every iteration, this runs in under a second for <em>n</em> up to about 30 <em>million</em>!</p>


blocks|key|5115110|text|果冻，5字节|type|header-two|depth|inlineStyleRanges|entityRanges|offset|length|data|5115111|2*æi@|code-block|syntax|javascript|5115112|在网上试试！|unstyled|5115113|先用n输入，x第二，如果不存在这样的逆，返回0。TIO链接中的脚注为您反转输入并格式化测试用例。|style|CODE|5115114|是如何工作的|5115115|2*æi@+-+Main+link.+Takes+n+on+the+left+and+x+on+the+right
2*++++-+Yield+2*n
++æi@+-+Modular+inverse+of+x,+modulo+2*n,+or+if+none+exists,+0.|entityMap|0|LINK|mutability|MUTABLE|url|https://github.com/DennisMitchell/jelly|1|https://tio.run/##y0rNyan8/99I6/CyTIf/1kqHlzvoP2pa4/7/f7ShgY6CaayOQrQ5gjYyADMMwCwA|2|INLINETEX|IMMUTABLE|teX|n|3|x|4^0|0|2|0|0|0|0|6|1|0|2|1|6|1|M|1|2|1|2|6|1|3|M|1|4|0|0^^$0|@$1|2|3|4|5|6|7|1A|8|@]|9|@$A|1B|B|1C|1|1D]]|C|$]]|$1|D|3|E|5|F|7|1E|8|@]|9|@]|C|$G|H]]|$1|I|3|J|5|K|7|1F|8|@]|9|@$A|1G|B|1H|1|1I]]|C|$]]|$1|L|3|M|5|K|7|1J|8|@$A|1K|B|1L|N|O]|$A|1M|B|1N|N|O]|$A|1O|B|1P|N|O]]|9|@$A|1Q|B|1R|1|1S]|$A|1T|B|1U|1|1V]|$A|1W|B|1X|1|1Y]]|C|$]]|$1|P|3|Q|5|6|7|1Z|8|@]|9|@]|C|$]]|$1|R|3|S|5|F|7|20|8|@]|9|@]|C|$G|H]]]|T|$U|$5|V|W|X|C|$Y|Z]]|10|$5|V|W|X|C|$Y|11]]|12|$5|13|W|14|C|$15|16]]|17|$5|13|W|14|C|$15|18]]|19|$5|13|W|14|C|$15|U]]]]

<h1><a href="https://github.com/DennisMitchell/jelly" rel="nofollow noreferrer">Jelly</a>, 5 bytes</h1>
<pre><code>2*æi@
</code></pre>
<p><a href="https://tio.run/##y0rNyan8/99I6/CyTIf/1kqHlzvoP2pa4/7/f7ShgY6CaayOQrQ5gjYyADMMwCwA" rel="nofollow noreferrer" title="Jelly – Try It Online">Try it online!</a></p>
<p>Takes input with <span class="math-container">\$n\$</span> first and <span class="math-container">\$x\$</span> second, returns <span class="math-container">\$0\$</span> if no such inverse exists. The Footer in the TIO link reverses the input for you and formats the test cases.</p>
<h2>How it works</h2>
<pre><code>2*æi@ - Main link. Takes n on the left and x on the right
2*    - Yield 2*n
  æi@ - Modular inverse of x, modulo 2*n, or if none exists, 0.
</code></pre>


blocks|key|6303135|text|间隙，39字节|type|header-two|depth|inlineStyleRanges|entityRanges|data|6303136|f:=function(x,n)return+1/x+mod+2%5En;end;|code-block|syntax|javascript|6303137|f(x,n)返回x模2%5En的逆，并给出一条错误消息|unstyled|offset|length|style|CODE|6303138|Error,+ModRat:+for+<r>/<s>+mod+<n>,+<s>/gcd(<r>,<s>)+and+<n>+must+be+coprime|6303139|如果没有逆的话。|entityMap^0|0|0|0|6|8|1|A|3|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|I|7|U|8|@$J|V|K|W|L|M]|$J|X|K|Y|L|M]|$J|Z|K|10|L|M]]|9|@]|A|$]]|$1|N|3|O|5|D|7|11|8|@]|9|@]|A|$E|F]]|$1|P|3|Q|5|I|7|12|8|@]|9|@]|A|$]]]|R|$]]

<h1>GAP, 39 bytes</h1>

<pre class="lang-GAP prettyprint-override"><code>f:=function(x,n)return 1/x mod 2^n;end;
</code></pre>

<p><code>f(x,n)</code> returns the inverse of <code>x</code> modulo <code>2^n</code> and gives an error message</p>

<pre><code>Error, ModRat: for &lt;r&gt;/&lt;s&gt; mod &lt;n&gt;, &lt;s&gt;/gcd(&lt;r&gt;,&lt;s&gt;) and &lt;n&gt; must be coprime
</code></pre>

<p>if no inverse exists.</p>


<p>Given two positive numbers <span class="math-container">\$x\$</span> and <span class="math-container">\$n\$</span> with <span class="math-container">\$x&lt;2^n\$</span>, write the shortest possible function to compute <span class="math-container">\$x^{-1} \mod 2^n\$</span>.  In other words, find <span class="math-container">\$y\$</span> such that <span class="math-container">\$xy=1 \mod 2^n\$</span>.</p>
<p>Your function must complete in a reasonable time for at least <span class="math-container">\$n=64\$</span>, so exhaustive search will not work.</p>
<p>If the inverse does not exist, you must indicate that to the caller somehow (throw an exception, return a sentinel value, etc).</p>
<p>If you're wondering where to start, try the <a href="http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm" rel="nofollow noreferrer">Extended Euclidean Algorithm</a>.</p>


Compute modular inverse

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

给定两个正数x和n与x<2^n，写出尽可能最短的函数来计算x^{-1} \mod 2^n。换句话说，找到y这样的xy=1 \mod 2^n。您的函数必须在至少n=64的合理时间内完成，因此详尽的搜索将无法工作。如果逆不存在，则必须以某种方式将其指示给调用方(抛出异常，返回一个哨位值等)。如果您想知道从哪里开始，请尝试扩展欧氏算法。

问计算模逆
EN

回答 7

Code Golf用户

Python，29字节

Code Golf用户

Python3.8 (预发行版)，25字节

Code Golf用户

Mathatica-22

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计算模逆EN

回答 7

Code Golf用户

Python，29字节

Code Golf用户

Python3.8 (预发行版)，25字节

Code Golf用户

Mathatica-22

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计算模逆
EN