c++ - 哈希和模块化算术

Question

设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].where0<=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。请提出一个有效的算法。谢谢！！！

Answer 1

这不是一个特别强的哈希。关于这个问题的唯一困难部分是带有单字母变量的钝符号并将问题指定为 7 元组。

每增加x一个增量h(x)。所以从到到a的总距离很简单。为栅栏问题添加一个，或者为了理智起见将问题指定为半开范围。xcd(d-c)/a