Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
统计
题目描述

给定一个大小为 $n$ 的可重集 $S = \{a_1,a_2, \dots, a_n \}$,满足 $a_i \geq 2$。对其进行若干次如下操作:

  1. 设 $p_i$ 为 $a_i$ 的最小素因子
  2. 令 $a_i \gets \frac{a_i}{p_i}$
  3. 将 $\prod_{i = 1}^{|S|}p_i$ 加入集合 $S$
  4. 将集合 $S$ 中的 1 删去

给定 $m$,求出进行了 $m$ 次操作后的集合 $S$,每个元素对 $10^9 + 7$ 取模后输出。

输入格式

第一行:两个整数 $n, m$。 第二行:$n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

第一行:一个整数 $k$,表示 $m$ 次操作后可重集的大小。 第二行:$k$ 个整数,表示可重集的元素对 $10^9 + 7$ 取模后的值。元素可按任意顺序输出。

样例输入 1
4 3
2 3 4 5
样例输出 1
3
2 4 15
样例输入 2
10 100
3 5 6 7 10 12 19 23 27 36
样例输出 2
6
3 23 45 120 126 684
数据范围

对于所有数据,满足 $1 \leq n \leq 10^4, 2 \leq a_i \leq 10^9, 1 \leq m \leq 10^{18}$。

对于子任务 1,满足 $n \times m < 10^5$。

对于子任务 2,满足 $n = 1$。

对于子任务 3,满足 $n \leq 100$。

对于子任务 4,满足 $n \leq 2000$。

对于子任务 5,无特殊限制。

大样例