c# - 反转已溢出的乘法运算

Question

给定代码:

uint Function(uint value)
{
  return value * 0x123456D;
}

输入值 0x300 会产生结果 0x69D04700。这只是结果的低 32 位。 给定结果 0x69D04700 和因子 0x123456D，是否可以快速检索满足 (value * 0x123456D) & 0xFFFFFFFF = 0x69D04700 的所有数字？

编辑:我显示的代码是伪代码 - 我无法扩大返回类型。

Answer 1

你需要的是模除法，它可以用欧几里德算法的一个版本来计算。在本例中，结果为 768。

这非常快 -- time (log n)² 即使对于一个简单的实现也是如此。 (如果您需要处理大量数据，我可以提供更好算法的引用。)

参见 extended Euclidean algorithm有关如何实现这一点的草图。