CF1371E2 Asterism (Hard Version)

这是该问题的困难版本。不同版本的区别在于 $n$ 和 $a_i$ 的约束条件。只有在所有版本的问题都被解决后，你才能进行 hack。 首先，Aoi 想出了如下的竞赛编程题目： Yuzu 是一个收集糖果的女孩。起初，她有 $x$ 颗糖果。还有 $n$ 个敌人，编号为 $1$ 到 $n$。第 $i$ 个敌人有 $a_i$ 颗糖果。 Yuzu 需要确定一个排列 $P$。排列是一个包含 $n$ 个 $1$ 到 $n$ 的不同整数的数组，顺序任意。例如，$\{2,3,1,5,4\}$ 是一个排列，但 $\{1,2,2\}$ 不是排列（$2$ 在数组中出现了两次），$\{1,3,4\}$ 也不是排列（因为 $n=3$，但数组中有数字 $4$）。 之后，她将按照以下规则与敌人进行 $n$ 场决斗： - 如果 Yuzu 拥有的糖果数不少于敌人 $P_i$ 的糖果数，她就赢得这场决斗，并获得 $1$ 颗糖果。否则，她输掉这场决斗，什么也得不到。 - Yuzu 在每场决斗中获得的糖果会在接下来的决斗中使用。 Yuzu 想要赢得所有决斗。请问有多少个合法的排列 $P$ 存在？ 这个问题对 Aoi 的朋友 Akari 来说太简单了，不够有趣。于是 Akari 基于上述想法提出了如下问题： 我们定义 $f(x)$ 为对于整数 $x$ 的合法排列数。 现在给定 $n$、$a$ 和一个质数 $p \le n$。我们称正整数 $x$ 是“好”的，如果 $f(x)$ 不能被 $p$ 整除。请找出所有“好”的整数 $x$。 你的任务是解决 Akari 提出的这个问题。

第一行包含两个整数 $n$ 和 $p$，$2 \le p \le n \le 10^5$。保证 $p$ 是质数（只有两个约数 $1$ 和 $p$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，$1 \le a_i \le 10^9$。

第一行输出“好”的整数 $x$ 的个数。 第二行按升序输出所有“好”的整数 $x$。 保证“好”的整数 $x$ 的数量不超过 $10^5$。

在第一个测试中，$p=2$。 - 如果 $x \le 2$，Yuzu 没有合法的排列。因此 $f(x)=0$，而 $0$ 能被 $2$ 整除，所以所有 $x \le 2$ 都不是“好”的。 - 如果 $x=3$，只有 $\{1,2,3\}$ 是 Yuzu 的合法排列。所以 $f(3)=1$，因此 $3$ 是“好”的。 - 如果 $x=4$，$\{1,2,3\}$、$\{1,3,2\}$、$\{2,1,3\}$、$\{2,3,1\}$ 都是 Yuzu 的合法排列。所以 $f(4)=4$，因此 $4$ 不是“好”的。 - 如果 $x \ge 5$，所有 $6$ 种排列都是合法的。所以 $f(x)=6$，因此所有 $x \ge 5$ 都不是“好”的。 所以，唯一的“好”数是 $3$。 在第三个测试中，对于所有正整数 $x$，$f(x)$ 都能被 $p=3$ 整除。 由 ChatGPT 4.1 翻译