1160번 - Random Number Generator 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 908 | 149 | 113 | 26.905% |
문제
홍준이는 통계학을 공부하다가 ‘무작위 추출’의 매력에 푹 빠졌고, 난수 발생기를 이용해 직접 ‘무작위 추출’을 한다. 홍준이는 일차 점화식으로 생성되는 수열을 이용한 난수 발생기가 적당하다고 생각했다. 수열을 만들기 위해서는 음이 아닌 정수 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의 값을 출력한다.
예제 입력 1
11 8 7 1 5 3
예제 출력 1
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번
- 문제를 번역한 사람: h0ngjun7
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호