c++ - 如果您有其他因子并且产品溢出，那么如何计算因子？

a * x = b

我有一个看似相当复杂的乘法/模数问题:如果我有a和我有b，如果它们都是32位双字(例如0-1 = FFFFFFFF，FFFFFFFF + 1 = 0)，如何计算x？
例如:

0xcb9102df * x = 0x4d243a5d

在这种情况下，x为0x1908c643。我发现了类似的问题，但前提不同。我希望有比给出的解决方案更简单的解决方案。

最佳答案

如果数字是奇数，则数字具有模乘以2的幂为模的逆。其他所有内容都是位移后的奇数(即使是零，也可能是零，所有位都移出了)。因此，有两种情况:

给定a * x = b

tzcnt(a) > tzcnt(b)没有解决方案

tzcnt(a) <= tzcnt(b)可解决，采用2tzcnt(a)解决方案

第二种情况是一种特殊情况，其中有一种解决方案，即odt a，即x = inverse(a) * b
更一般而言，x = inverse(a >> tzcnt(a)) * (b >> tzcnt(a))是一种解决方案，因为您将a写为(a >> tzcnt(a)) * (1 << tzcnt(a))，所以我们将左因子取反，然后将其保留为结果的一部分(无论如何都不能取消)，然后乘以剩余的余数即可得到它。直到b。显然，它仍然仅在第二种情况下有效。如果需要，可以通过填写所有tzcnt(a)最高位的可能性来枚举所有解决方案。

剩下的唯一事情就是得到反函数，您可能已经在其他答案中看到了它，不管它是什么，但是为了完整起见，您可以按如下方式对其进行计算:(未经测试)

; input x
dword y = (x * x) + x - 1;
dword t = y * x;
y *= 2 - t;
t = y * x;
y *= 2 - t;
t = y * x;
y *= 2 - t;
; result y

关于c++ - 如果您有其他因子并且产品溢出，那么如何计算因子？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/36538155/