해시 및 모듈러 Arthmetic

Question

은 h(y)가 (a*y+b)mod m으로 정의 된 함수라고하자. 따라서 h(y) 값을 취할 수 있습니다 from 0 to m-1. 이제 우리는 7 정수 - a,b,x,n,c,d,m 주어집니다. 예를 들어

1 ≤ m ≤ 10^15, c ≤ d < m, a,b < m, x+n ≤ 10^15, and a*(x+n) + b ≤ 10^15 

: 우리의 임무는 h(x+i)의 값이 [c,d] 이야기 해봐 0<=i<=n 정수 제한의 범위 내에 있도록 h(x),h(x+1),h(x+2)...h(x+n)이의 총 수를 찾는 것입니다. 입력 set {1,0,0,8,0,8,9} 출력은 9 여야합니다. 효율적인 알고리즘을 제안하십시오. 감사!!!

Answer 1

특히 강한 해시는 아닙니다. 이 문제에 대한 유일한 어려운 부분은 단일 문자 변수를 사용하고 7- 튜플로 문제를 지정하는 무명의 표기법입니다.

각 증가분은 x입니다. h(x)은 a입니다. d-c 단순히 (d-c)/a이다에서 따라서 x 따라 총 거리를 얻을 수 있습니다. 펜스 포스트 (fencepost) 문제에 대해 하나를 추가하거나 온전한 목적을 위해 반 개방 범위의 문제를 지정하십시오.