模乘逆

Question

您的任务是给出两个整数，a和b计算模b的模乘逆，如果它存在的话。

a模b的模逆是一个像ac ≡ 1 (mod b)这样的数字c。对于任何一对b和a，这个数字都是唯一的模b。只有当a和b的最大公因子是1时，它才会存在。

如果您需要更多关于该主题的信息，可以参考模块乘性逆的维基百科页面。

输入输出

输入是以两个整数或两个整数列表的形式给出的。您的程序应该输出单个数字、间隔0 < c < b中的模乘逆或表示没有逆的值。该值可以是任何值，但范围(0,b)中的数字除外，也可能是例外。但是，对于没有逆的情况，这个值应该是相同的。

可以假定为0 < a < b

规则

• 程序应该在某个时候完成，并且应该在60秒内解决每个测试用例。
• 适用标准漏洞

测试用例

下面的测试用例以a, b -> output格式给出

1, 2 -> 1
3, 6 -> Does not exist
7, 87 -> 25
25, 87 -> 7
2, 91 -> 46
13, 91 -> Does not exist
19, 1212393831 -> 701912218
31, 73714876143 -> 45180085378
3, 73714876143 -> Does not exist

评分

这是代码高尔夫，所以每种语言的最短代码获胜。

这和这是相似的问题，但都要求特定的情况。

Answer 1

Mathematica，14字节

必修数学内建：

ModularInverse

它是一个接受两个参数(a和b)的函数，如果它存在，则返回mod b的逆函数。如果没有，则返回错误ModularInverse: a is not invertible modulo b.。

Answer 2

Python 2，34字节

f=lambda a,b:a==1or-~b*f(-b%a,a)/a

在网上试试！

递归函数，它为True提供print f(1,2) (我认为这是可以接受的)，并为无效输入提供错误。

我们正试图在a\cdot x\equiv 1\pmod{b}找到x。

这可以写成a\cdot x-1=k\cdot b，其中k是一个整数。

以\mod{a}为例给了-1\equiv k\cdot b\pmod{a}。移动负值给出了-k\cdot b\equiv1\pmod{a}，在这里我们必须对k进行求解。

考虑到它与最初场景的相似之处，允许我们通过使用k调用函数来解决f(-b\%a,a)问题(因为Python给出了带有否定参数的模块的正值)。

该程序一直循环到a变为1，这只有在原始a和b是相互对应的情况下(即存在乘法逆)，或者以由除以0引起的错误结束。

k的这个值可以在方程a\cdot x-1=k\cdot b中被替换，从而给出x作为\frac{k\cdot b+1}{a}。

Answer 3

果冻，2字节

æi

在网上试试！

这将使用内置的模块逆，而对于没有模逆的返回0。

果冻，7字节

R×%⁸’¬T

在网上试试！

在没有模逆的情况下输出空集(表示为空字符串)。对于最大的测试用例，TIO上内存不足，但是应该有足够的内存。

是如何工作的

R×%⁸’¬T  
R        Generate range of b
 ×       Multiply each by a
  %⁸     Mod each by b
    ’    Decrement (Map 1 to 0 and all else to truthy)
     ¬   Logical NOT
      T  Get the index of the truthy element.

如果您想为更大的测试用例工作，请尝试这个(相对不太高的)版本，它需要大量的时间而不是内存：

果冻，9字节

×⁴%³’¬ø1#

在网上试试！

是如何工作的

×⁴%³’¬ø1#
        #   Get the first
      ø1      one integer
            which meets:
×⁴            When multiplied by a
  %³          And modulo-d by b
    ’         Decrement
     ¬        Is falsy