Хеш и модульная артметика
Позволять h(y) быть функцией, определенной как (a*y+b)mod m. Так h(y) может принимать значения from 0 to m-1.
Теперь нам дано 7 целых чисел a,b,x,n,c,d,m, Наша задача — найти общее количество h(x),h(x+1),h(x+2)...h(x+n) такой, что значение h(x+i) попадает в диапазон [c,d].где 0<=i<=n
Целочисленные ограничения:
1 ≤ m ≤ 10^15, c ≤ d < m, a,b < m, x+n ≤ 10^15, and a*(x+n) + b ≤ 10^15
Например.
для ввода set {1,0,0,8,0,8,9} вывод должен быть 9. Пожалуйста, предложите эффективный алгоритм. Спасибо!!!
Решение
Это не особенно сильный хэш. Единственная сложная часть этой проблемы — это тупые обозначения с однобуквенными переменными, указывающие на проблему как 7-кортеж.
Каждый шаг x увеличивается h(x) от a, Поэтому общее расстояние вдоль x чтобы получить от c в d это просто (d-c)/a. Добавьте один для проблемы забора или укажите проблему с полуоткрытым диапазоном ради здравомыслия.
Другие решения