Можно ли получить исходное значение числа после нескольких умножений **с переполнением**? ⇐ C++

[Anonymous]

Резюме: Предположим, у меня есть беззнаковое целое число. Затем я умножаю его несколько раз (и происходит переполнение, что и ожидалось). Тогда можно ли «вернуть» исходное значение обратно?

Подробнее:
Все дело в хэше Рабина-Карпа. Что мне нужно сделать: у меня есть хэш длинной строки, например: «abcd». Затем у меня есть хеш для более короткой подстроки, например «cd». Как вычислить хеш «ab» с помощью O(1), используя два заданных хэша?
Что у меня есть сейчас в качестве алгоритма:

• вычесть хэш "cd" из хеша "abcd" (удалить последние элементы из полинома)
• разделить хеш "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 — небольшое число). А если нет - это не работает.
Есть какой-нибудь трюк или что-то в этом роде?
P.S. Тег c++ создан из-за переполнения числа, поскольку он специфичен (и отличается от Python, схемы или чего-то еще)

Подробнее здесь: https://stackoverflow.com/questions/592 ... ltiplicati