Bézout的身份

Question

Bézout的身份

简介

两个整数A，B的GCD是最大的正整数，它把两个整数除以，不留下余数。由于欧几里得的性质，每个整数N可以除以另一个整数M，如下所示：

存在对u，v，这样我们就可以写：

由于这些对的数量是无限的，我们想找出特殊的对。事实上，有两个这样的对(A，B不是零)是令人满意的。

例如，商品、商业、商业、金融、金融等领域，例如，商业、金融等领域，如:商品、金融、商业、金融、商业、商业、金融等领域，如:商品、商品、商业、金融等领域，如:商品、商品、商业、金融、金融、商业、金融等领域，如:商品、商品、商业、金融、商业、商业、金融等领域，如:商品、金融等领域，如:商品、商品、金融、金融、商业、金融等领域的产品，如:商品、商业、金融、

挑战

这个挑战的目标是找到满足上述约束的(有序)系数对(u，v)，其中u必须是正的。这会将输出缩小到唯一的一对。

输入

我们可以假设输入是正的，而且A总是大于B (A > B)。

输出

我们的程序/函数的输出必须是质询中指定的(有序)对。

规则

不能使用内置的扩展欧几里得算法(例如，在数学中，允许使用GCD，而不允许使用ExtendedGCD )，这将导致5,3次失败。

答案可能是完整的程序(通过STDIN或类似的输入，通过STDOUT输出)或函数(返回对)。

在对(u，v)旁边不得有任何输出，允许拖尾换行符或空格。(括号或逗号可以)

这是代码高尔夫，所有的标准漏洞都被禁止，而字节数最低的程序获胜。

示例

(A, B) -> (u, v)
(42, 12) -> (1, -3)
(4096, 84) -> (4, -195)
(5, 3) -> (2, -3)
(1155, 405) -> (20, -57)
(37377, 5204) -> (4365, -31351)
(7792, 7743) -> (7585, -7633)
(38884, 2737) -> (1707, -24251)
(6839, 746) -> (561, -5143)
(41908, 7228) -> (1104, -6401)
(27998, 6461) -> (3, -13)
(23780, 177) -> (20, -2687)
(11235813, 112358) -> (8643, -864301)

Answer 1

Haskell，51字节

a#b=[(u,-v)|v<-[1..],u<-[1..v],gcd a b==u*a-v*b]!!0

用法示例：27998 # 6461 -> (3,-13)。

这是一种蛮力方法，它查找u和v的所有组合，这些组合是u命令的有效解决方案，并选择第一个解决方案。这需要一些时间来运行大型|v|。

Answer 2

Ruby，83字节

我认为有几种方法可以微调和高尔夫这个解决方案，但我喜欢到目前为止。也许接下来我会尝试一个扩展的欧几里德算法解决方案。

->x,y{a=b=0;y.downto(0).map{|u|(-x..0).map{|v|a,b=u,v if u*x+v*y==x.gcd(y)}};p a,b}

是如何工作的

这段代码以u从y到0的循环开始，从-x到0的内环由v开始，其中我们检查每个u和v是否为u*x+v*y == gcd(x, y)。由于在此过程中可能有多个匹配(这使用了非常详尽的搜索)，所以我们从0开始，因此当我们得到最后一个多个匹配时，它是|u|和|v|最接近0的匹配。

def bezout(x,y)
  a=b=0
  y.downto(0).each do |u|
    (-x..0).each do |v|
      if u*x + v*y == x.gcd(y)
        a,b=u,v
      end
    end
  end
  p a,b
end

Answer 3

Mathematica，80字节

f@l_:=Mod@@NestWhile[{Last@#,{1,-Quotient@@(#.l)}.#}&,{{1,0},{0,1}},Last@#.l>0&]

解释

扩展欧氏算法在这里是用Nest样式使用的。将系数存储在数组中的方法使使用Dot成为可能。

另一种可能的表示形式是简单地使用符号表达式，比如u a - v b和{a->19, b->17}。这种表示方式利用了Mathematica的特性，而且很有趣，但以字节表示的时间要长得多。

测试用例

f[{5, 3}]              (* {2, -3} *)
f[{42, 12}]            (* {1, -3} *)
f[{11235813, 112358}]  (* {8643, -864301} *)