COCI 2012/2013 - 번역 : functionx <br>2013.02.23 모의테스트4- 전염병(DLAKAVA) > 문제은행 : 정보올림피아드&알고리즘




1628 : 전염병(DLAKAVA)

제한시간
2000 ms   
메모리제한
32 MB   
해결횟수
13 회   
시도횟수
47 회   

문제

정올 도시에는 M명의 사람들이 있고, 각 사람들은 0 이상 M-1 이하의 고유번호를 가지고 있다.

어느 날, 정올 도시에 이상한 전염병이 퍼지기 시작했다. 

이 전염병은 이상하게도 정확히 하루 동안만 발병하고, 여러 번 발병할 수 있다. 

첫 번째 날 전염병에 걸린 사람은 N명인데, 이 사람들을 특별히 “최초”라고 하자.

 

이 전염병은 다음과 같은 방식으로 옮겨진다.


A = 전염병에 걸린 사람의 고유번호, B = “최초”인 사람의 고유번호 (A와 B가 같을 수 있다)

라고 하면 고유번호가 정확히 A × B를 M으로 나눈 나머지와 같은 사람은 다음 날에 전염병에 걸린다.


예를 들어, 정올 도시에 101명의 사람들이 있고, “최초”로 전염병에 걸린 사람의 고유번호가 5, 50이라면, 

두 번째 날에는 5×5=25, (5×50) mod 101=48, (50×50) mod 101=76번 고유번호를 가진 사람이 전염병에 걸리게 된다. 

또, (48×50) mod 101=77이기 때문에, 77번 고유번호를 가진 사람은 세 번째 날에 전염병에 걸린다. 

 

K가 주어질 때, K번째 날에 전염병에 걸리는 사람들을 구하는 프로그램을 작성하여라.


입력형식

첫 번째 줄에는 K, M, N이 주어진다. (1 ≤ K ≤ 1018, 3 ≤ M ≤ 1,500, N < M)

두 번째 줄에는 첫 번째 날 전염병에 걸린 사람들의 고유번호가 오름차순으로 주어진다.


출력형식

K번째 날에 전염병에 걸린 사람들의 고유번호를 오름차순으로 출력한다.


입력 예

1 100 3 
1 2 3

출력 예

1 2 3

Hint!

입력 예 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




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP