← 返回题目列表

Codeforces · 703/E

E. 米什卡和除数

中文机器翻译题面 查看原题

在玩完她美丽的数组后,米什卡决定学习一些数学。在学习了如何乘法、除法以及什么是整除性之后,她现在有兴趣解决以下问题。

给定整数 k 和 n 个整数的数组 a1, a2, ..., an。您要找到数组元素的非空子序列,使其元素的乘积可被 k 整除,并且包含尽可能少的元素数。

正式地,您需要找到一个索引序列 1 ≤ i1 < i2 < ... < im ≤ n,使得 $$\prod_{j=1}^{m}a_{i_j}$$ 可以被 k 整除,而 m 是所有此类变体中可能的最小值。

如果有多个这样的子序列,则应从其中选择一个,使其元素之和最小。

Mishka很快解决了这个问题。你会这样做吗?

输入

输入的第一行包含两个整数 n 和 k (1 ≤ n ≤ 1 000, 1 ≤ k ≤ 1012)。

输入的第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 1012) - 数组元素。

输出

在第一行打印单个正整数 m — 所需序列中的元素数量。

在第二行中打印 m 个不同的整数 - 给定数组元素的索引序列,应将其纳入所需的序列中。

如果有多个这样的子序列(例如,具有最小可能元素数量和最小可能元素总和的子序列),则可以打印其中任何一个。

如果没有这样的子序列,则在唯一的行中打印 - 1。

示例

输入 #1

5 60
2 4 6 5 2

输出 #1

3
4 3 1