Как при двойном хэшировании последовательность проб является перестановкой?

Question

[TrumpDonald]

Добрый день, я не могу понять. Допустим есть двойное хэширование h(k,i)=(h1(k)+i*h2(k)) mod n. Есть утверждение что последовательность проб соответствующих ключу k, является перестановкой множества {0,1,...,n-1} тогда и только тогда, когда h2(k) взаимно просто с n. Приведите пожалуйста хотя бы 1 пример что бы утверждение было верно.

Comments

[Владимир Олохтонов]

А можно ознакомиться с источником этой формулировки?

Вот здесь получше описан процесс: https://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%...

Answer 1

[longclaps]

Чего уж проще. Пусть n==2^t, так обычно и бывает. Тогда h2(k)==2*k+1 - нечетное число, завсегда взаимно простое с n.
Подставьте и проверьте.