反转已经溢出的乘法运算

Question

鉴于代码:

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

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

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

Answer 1

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

即使对于简单的实现来说，这也非常快——时间 (log n ) ^{2 。}（如果您需要处理大量数据，我可以提供更好的算法的参考。）

请参阅扩展欧几里得算法以了解如何实现此算法的草图。