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] 范围内.哪里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。请建议一个有效的算法。谢谢!!!

Answer 1

这不是一个特别强的哈希值。这个问题唯一困难的部分是使用单字母变量的钝表示法并将问题指定为 7 元组。

每次增加x都会使h(x)增加a。因此，沿 x 从 c 到 d 的总距离就是 (d-c)/a 。为栅栏柱问题添加一个，或者为了保持理智而用半开范围指定问题。