문제
정올 도시에는 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
입력
1 100 3
1 2 3
출력
1 2 3
예제2
입력
2 100 3
1 2 3
출력
1 2 3 4 6 9
예제3
입력
10 101 2
5 50
출력
36 44 57 65
힌트
출처
COCI 2012/2013 - 번역 : functionx
2013.02.23 모의테스트4
2013.02.23 모의테스트4