3989번 - 유행성 독감 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 210 | 57 | 47 | 46.078% |
문제
상근이가 살고 있는 마을에 유행성 독감이 전염되기 시작했다. 마을에는 총 M명이 살고 있고, 각 사람은 0번부터 M-1번까지 번호가 매겨져 있다. 독감은 딱 하루 동안만 걸린다. 따라서, 한 사람이 여러 번 독감에 걸릴 수 있다.
독감은 다른 마을에 놀러갔다가 돌아온 사람들이 전염시켰다. 이 사람들의 번호는 모두 알려져 있다. 첫째 날에 독감에 걸린 사람은 이 사람들 뿐이다. 독감은 이 사람들에 근거해서 전염이 된다.
둘째 날부터 각각의 날에 독감에 걸린 사람은 다음과 같은 규칙을 갖는다.
이전 날에 독감에 걸린 사람 a와 첫째 날에 걸린 사람 b를 곱한 뒤 M으로 나눈 나머지 번호를 갖는 p는 모두 독감에 걸린다.
즉, (a * b) mod M = p 에 해당하는 p는 모두 독감에 걸린다.
a와 b는 같아도 된다. 예를 들어, 마을에 101명이 살고 있고, 첫째 날에 독감에 걸린 사람이 5와 50이라고 하자. 둘째 날에 독감에 걸린 사람은 25, 48 (250 mod 101), 76 (2500 mod 101)이 된다. 또, 셋째 날에 독감에 걸린 사람 중 한 명은 77 이다. ((48 * 50) mod 101)
K일에 독감에 걸려 있는 사람을 모두 구하는 프로그램을 작성하시오.
입력
첫째 날에 K, M, N이 주어진다. (1 ≤ K ≤ 1018, 3 ≤ M ≤ 1500, N < M) N은 첫째 날 독감에 걸린 사람의 수이다.
둘째 줄에는 첫째 날 독감에 걸린 사람이 공백으로 구분되어 주어진다.
출력
첫째 줄에 K일에 독감에 걸려있는 사람의 번호를 공백으로 구분하여 오름차순으로 출력한다.
예제 입력 1
1 100 3 1 2 3
예제 출력 1
1 2 3
예제 입력 2
2 100 3 1 2 3
예제 출력 2
1 2 3 4 6 9
예제 입력 3
10 101 2 5 50
예제 출력 3
36 44 57 65
출처
Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #4 5번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호