c++ - 是否有可能在多次乘法**溢出**后得到一个数字的原始值？

Question

总结:有没有办法做到这一点？这就是我的意思:假设我有一个 unsigned int 数字。然后我乘以它几次(并且有溢出，这是预期的)。那么是否可以“还原”原始值？

---

详细信息:

都是关于Rabin-Karp rolling hash的.我需要做的是:我有一个长字符串的哈希值——例如:“abcd”。然后我有一个较短的子字符串的散列 - 例如“cd”。如何使用给定的两个哈希值以 O(1) 计算“ab”哈希值？

我现在拥有的算法:

• 从“abcd”散列中减去“cd”散列(从多项式中删除最后一个元素)
• 将“abcd”散列除以p ^ len( "cd")，其中p 是基数(质数)。

所以这是:

a * p ^ 3 + b * p ^ 2 + c * p ^ 1 + d * p ^ 0 - abcd

c * p ^ 1 + d * p ^ 0 - cd

ab 得到:

( 
  ( a * p ^ 3 + b * p ^ 2 + c * p ^ 1 + d * p ^ 0 ) -
  ( c * p ^ 1 + d * p ^ 0 ) 
)
/ ( p ^ 2 )
= a * p ^ 1 + b * p ^ 0

如果我没有溢出(如果 p 是小数字)，这会起作用。但如果不是 - 它不起作用。

有什么技巧吗？

附言c++ 标签是因为数字的溢出，因为它是特定的(并且不同于 python，scheme 或 sth)

Answer 1

不知道溢出部分，但有一种方法可以取回原始值。

中国剩余定理帮了大忙。让我们调用 h = abcd - cd。 G 是值，h，没有溢出，G = h + k*2^32，假设溢出只是 %2^32 .因此 ab = G/p^2。

G = h (mod 2^32)
G = 0 (mod p^2)

如果 p^2 和 2^32 互质。本页 Chinese Remainder Theorem , 给了我们

G = h * b * p^2 (mod 2^32 * p^2)

其中 b 是 p^2 模 2^32 的模乘逆，b * p^2 = 1 (mod 2^32)。计算出 G 后，只需除以 p^2 即可找到 ab。

我希望我没有犯任何错误......