Nim乘法

Question

背景

如果您做了大量的代码高尔夫球，您可能知道位异或操作。给定两个整数，它在两个输入不同的位上给出了另一个带有1s的整数。例如，1010 XOR 0011 = 1001。

这在博弈论中是非常有用的，在博弈论中，它更被称为“尼姆和”。如果你有两个游戏的总和(也就是说，你一次在一个游戏中移动)，那么这个位置的价值就是每个游戏中位置值的尼姆和。

但我们可以更进一步。利用nim加法和适当的尼姆乘法定义，我们可以从非负整数中形成一个域。因此，挑战是高尔夫尼姆乘法。

定义

Nim乘法遵循以下规则：

费马2-幂n= (2^(2^k))的nim乘积是普通乘积。

费马2-幂n与其自身的nim乘积为3n/2.

Nim增殖分布在nim加法上。

Nim乘法是可交换的和结合的(和nim加法一样)。

乘法恒等式为1(加式恒等式为0)。

任何非负整数都可以写成二次方的nim和，任意二次方可以写成不同Fermat数的乘积，这就足以定义所有非负整数的nim乘法。

示例

这都是非常抽象的，所以让我们来看看一个例子。我将使用+来表示nim加法(XOR)和用于nim乘法的*。

6 * 13
= (4 + 2) * (8 + 4 + 1)
= (4 + 2) * ((4 * 2) + 4 + 1)
= (4 * 4 * 2) + (4 * 2 * 2) + (4 * 4) + (4 * 2) + (4 * 1) + (2 * 1)
= (6 * 2) + (4 * 3) + 6 + 8 + 4 + 2
= ((4 + 2) * 2) + 12 + 6 + 8 + 4 + 2
= (4 * 2) + (2 * 2) + 12 + 6 + 8 + 4 + 2
= 8 + 3 + 12 + 6 + 8 + 4 + 2
= 15

附加测试用例

4, 4 -> 6
4, 3 -> 12
4, 7 -> 10
2, 4 -> 8
2, 3 -> 1
1, 42 -> 42

挑战

编写一个程序或函数，给出任意形式的两个非负整数，计算它们的nim积。

这是密码-高尔夫，所以最短的提交获胜。

Answer 1

尼姆，120字节

proc f(a,b:int):int=
 var s={0..a*b}
 for i in 0..<a*b:s=s-{f(i%%a,i/%a)xor f(a,i/%a)xor f(i%%a,b)}
 for i in s:return i

在网上试试！

好吧，这可能很疯狂，但是有人必须在尼姆做尼姆乘法.

这是维基百科的标准算法。问题是我不懂这门语言，所以不得不马上学习基础知识。特别是，我感到惊讶的是，-=和min没有在集合中工作，我找到的提取最小值的最佳方法是使用迭代器并返回第一个值。希望尼姆专家能帮助我改善这一点。

Answer 2

Python 2，85字节

f=lambda x,y:min(set(range(x*y+1))-{f(i%x,i/x)^f(x,i/x)^f(i%x,y)for i in range(x*y)})

在网上试试！

慢得要命。递归计算mex({α‘β⊕αβ’⊕α‘β’：α‘<α，β’<β})。

Answer 3

皮斯，21字节

Mf-TsmmxxgkdgkHgGdGH0

游行示威

使用nim乘法的最小排除元素公式，如给定的这里。

使用两个嵌套映射对所有较小的值(mm ... GH)进行迭代，然后将结果扁平化(s)。聪明的部分是f-T ... 0，在这里我们从0向上迭代整数，以找到上面提到的集合中没有包含的第一个整数。通过这样做，我们不需要计算迭代上限，只需节省几个字节。

最后，函数g计算nim乘积。