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

これは特に強力なハッシュではありません。この問題の唯一の難しい部分は、1 文字の変数を使用した鈍い表記と、問題を 7 タプルとして指定していることです。

の増分ごとに がx増加h(x)しaます。したがって、xから までcの総距離dは単純に(d-c)/aです。フェンスポストの問題に 1 つ追加するか、健全性のために半開きの範囲で問題を指定します。