6523번 - 요세푸스 한 번 더! 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 179 | 88 | 53 | 49.074% |
문제
프로 드링커 상근이는 술을 마실때, 요세푸스 문제와 같은 순서로 술을 마신다. 요세푸스 문제를 천 번 넘게 푼 상근이는 머리 속으로 가장 마지막에 술을 마시는 사람의 위치를 계산할 수 있다. 따라서, 같이 술을 마시는 친구들은 상근이를 이기기 위해서 술을 마시는 새로운 순서를 제시했다.
먼저, 원탁에 모두 앉는다. 총 N명이 원탁에 앉았다면, 각 사람의 번호는 0번부터 N-1번이 된다.
요세푸스 문제와 다르게 다음 사람을 고르기 위해서 두 숫자 a와 b를 이용한다. 현재 선택된 사람의 번호가 x라면, 다음 사람의 번호는 ax2+b mod N이 된다.
가장 처음 시작하는 사람의 번호는 0번이다. 다음 사람의 번호는 위의 식을 이용해서 고른다.
각 사람은 한 번의 기회를 더 받을 수 있다. 즉, 한 번 걸리면 술을 마시는 것이 아니고, 두 번 걸렸을 때, 술을 마시는 것이다.
만약, 어떤 사람이 세 번 걸렸다면, 그 즉시 모두 자리를 박차고 일어나 집으로 간다.
N과 a, b가 주어졌을 때, 술을 마시지 않고 집으로 가는 사람의 수를 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 세 숫자 N, a, b가 공백으로 구분되어져 있다. (2 ≤ N ≤ 109, 0 ≤ a, b < N) 또, 첫 사람이 술을 마시기 위해 필요한 단계의 수는 106보다 작다. 입력의 마지막 줄에는 0이 하나 주어진다.
출력
각 테스트 케이스에 대해서, 술을 마시지 않고 집으로 가는 사람의 수를 출력한다.
예제 입력 1
2 1 1 5 1 1 10 3 7 101 9 2 698253463 1 181945480 1000000000 999999999 999999999 0
예제 출력 1
0 2 4 96 698177783 999999994
힌트
요세푸스 문제는 1158번을 참고하면 된다.
출처
Contest > University of Ulm Local Contest > University of Ulm Local Contest 2006 F번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호