시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 64 11 9 52.941%

문제

홍준이는 통계학을 공부하다가 ‘무작위 추출’의 매력에 푹 빠졌고, 난수 발생기를 이용해 직접 ‘무작위 추출’을 한다. 홍준이는 일차 점화식으로 생성되는 수열을 이용한 난수 발생기가 적당하다고 생각했다. 수열을 만들기 위해서는 음이 아닌 정수 m, a, c, X0이 필요하다. 수열 <Xn>의 점화식은 다음과 같다:

Xn+1 = (aXn + c) mod m

"A mod m"이라는 말은 A를 m으로 나눈 나머지를 뜻한다.

최종적으로, Xn을 양의 정수 g로 나눈 나머지가 난수로 사용한다. 따라서 생성된 난수는 0, 1, …, g-1사이의 값을 가지게 될 것이다.

착한 명우는, 친구 홍준이의 속마음을 읽고, 난수 발생기를 만들어주려고 한다. 명우를 도와 홍준이에게 줄 난수 발생기 프로그램을 작성하시오.

입력

첫째 줄에 6개의 정수 m, a, c, X0, n, g (m, a, c, X0, n ≤ 1018, g ≤ 108)가 차례대로 주어진다. a, c, X0는 음이 아닌 정수이고 m, n, g는 양의 정수이다.

출력

첫째 줄에 Xn mod g의 값을 출력한다.

예제 입력

11 8 7 1 5 3

예제 출력

2

힌트

예제 입력으로 생성되는 수열 <Xn>을 구해보면 아래와 같다.

k 0 1 2 3 4 5
Xk 1 4 6 0 7 8

따라서 답은 X5 mod g = 8 mod 3 = 2이다.

출처

Olympiad > National Olympiad in Informatics (China) > NOI 2012 1번

  • 문제를 번역한 사람: appa