무작위 간격

의사난수 생성기(RNG)는 통계 계산에서 널리 쓰인다. 그중 가장 단순하고 흔한 것이 선형 합동 생성기로, 바로 앞 값으로부터 $n$ 번째 수 $R_n$ 을 다음과 같이 만든다.

$R_n = (a \cdot R_{n-1} + c) \bmod m$

여기서 $a$ , $c$ , $m$ 은 고정된 상수이고 $R_0$ 은 시작 씨앗값이다. 예를 들어 $a = 15$ , $c = 7$ , $m = 100$ , $R_0 = 1$ 이면 수열은 $1, 22, 37, 62, 37, 62, \dots$ 이다.

이런 생성기는 빠르고, 상수를 잘 고르면 좋은 난수열을 만든다. 품질을 재는 한 가지 척도는 수열이 만들어 내는 값들 사이의 가장 큰 간격이다. 수열에 등장하는 서로 다른 값들의 집합을 생각하고, 그중 다음 두 조건을 만족하는 값 $R_i < R_j$ 를 찾아라.

$R_i < R_k < R_j$ 인 값 $R_k$ 가 수열에 존재하지 않는다(즉 $R_i$ 와 $R_j$ 는 서로 다른 값들 중에서 이웃한다).
차이 $R_j - R_i$ 가 최대이다.

이 최대 차이를 출력하라. 수열이 만들어 내는 서로 다른 값이 하나뿐이면 $0$ 을 출력한다.

네 정수 $a$ , $c$ , $m$ , $R_0$ 이 주어진다.

위에서 설명한 최대 차이를 정수 하나로 출력한다.