P13417 [COCI 2012/2013 #4] DLAKAVAC

在遥远的 Xanadu 城市，一场由“毛流感”病毒引发的流感疫情爆发了。该市共有 $M$ 位居民，每位居民都有一个唯一的个人编号，编号范围为 $0$ 到 $M-1$。感染这种流感后会持续恰好一天，而且由于病毒变异极快，居民在同一季节内可以多次感染（不会获得持久免疫）。 疫情爆发的第一天，流感由一批被称为“初始病人”（init-patients）的居民从另一个遥远国家带入，他们的编号是已知的。流感的传播以这些初始病人为基础。之后的每一天，编号为 $p$ 的居民会在且仅在存在编号为 $a$ 的居民在前一天感染，并且存在编号为 $b$ 的初始病人，使得： $$ (a \times b) \bmod M = p $$ 其中 $a$ 和 $b$ 可以相同，也可以不同。例如，假设镇上有 $101$ 人，初始病人编号为 $5$ 和 $50$。第一天，初始病人自然感染。第二天，感染者为 $25$、$48$（$250 \bmod 101$）、$76$（$2500 \bmod 101$）。第三天，感染者之一为 $77$，因为 $(48 \times 50) \bmod 101 = 77$。 请问第 $K$ 天会有哪些人感染流感？

第一行输入三个正整数 $K$、$M$ 和 $N$（$1 \leq K \leq 10^{18}$，$3 \leq M \leq 1500$，$N < M$）。 第二行输入 $N$ 个两两不同、递增、且不超过 $M-1$ 的非负整数，表示初始病人的编号。

输出一行，按升序输出第 $K$ 天感染流感的所有居民编号，用空格分隔。

翻译由 ChatGPT-4.1 完成。