무작위 숫자 생성기(random number generator)는 여러 방면에서 상당히 중요한 역할을 한다.

다음과 같은 방법의 무작위 숫자 생성기가 있다고 하자, 만들어진 숫자의 길이가 최대 D자리가 되게 하고자 한다. 우선 10^D 보다 임의의 작은 소수(prime number) P를 선택하고 임의의 자연수 A와 B를 선택한다. 그 다음에 0 이상 P-1 이하의 임의의 정수 S를 선택한다. 무작위 숫자 생성기에서 처음 생성되는 숫자는 S이다. 그 다음에 다음 숫자 S'를 생성할 때 부터는 다음의 수식을 이용한다.

S' := (A*S + B) mod P.

위에서 mod는 P로 나눈 나머지를 뜻하며, 위의 수식을 통해서 구한 S'은 다음에 생성되는 숫자가 된다. 그런 다음 S를 S'로 대치하고, 위의 수식을 반복하여 다음에 발생할 숫자를 구하게 된다.

예를 들어 D = 2 이고, P = 3 이며, A = 1, B = 1, S = 0 일 경우 생성되는 무작위 숫자들은 다음과 같다.

0 1( (1*0+1) mod 3 ) 2( (1*1+1) mod 3 ) 0( (1*2+1) mod 3 ) 1( (1*0+1) mod 3 ) ...

P, 그리고 A와 B, 그리고 S를 알지 못하는 상태에서 위의 방법으로 생성된 연속된 구간의 K개의 숫자가 주어졌을 때 다음에 생성되는 숫자가 무엇인지 알아내는 프로그램을 작성하라. 단, 발생하는 무작위 숫자의 범위에 대한 D는 주어진다.

제출파일의 이름은 2274.cpp로하고 실행시간은 5초를 넘을 수 없다.

#2274 upload 2 done 2 how_to_reg 2

무작위 숫자 생성기 timer 5s memory - MB

#2274

무작위 숫자 생성기 5s - MB