Longest Subsequence

题意翻译

给出n个数，要求选出尽可能多的数，满足它们的最小公倍数不大于m。允许数列里没数，此时这个数列的最小公倍数为1。 $n,m<={10}^{6}$ $a_i <= {10}^{9} $ 感谢@fs6y 提供的翻译

题目描述

You are given array $ a $ with $ n $ elements and the number $ m $ . Consider some subsequence of $ a $ and the value of least common multiple (LCM) of its elements. Denote LCM as $ l $ . Find any longest subsequence of $ a $ with the value $ l<=m $ . A subsequence of $ a $ is an array we can get by erasing some elements of $ a $ . It is allowed to erase zero or all elements. The LCM of an empty array equals $ 1 $ .

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1<=n,m<=10^{6} $ ) — the size of the array $ a $ and the parameter from the problem statement. The second line contains $ n $ integers $ a_{i} $ ( $ 1<=a_{i}<=10^{9} $ ) — the elements of $ a $ .

输出格式

In the first line print two integers $ l $ and $ k_{max} $ ( $ 1<=l<=m,0<=k_{max}<=n $ ) — the value of LCM and the number of elements in optimal subsequence. In the second line print $ k_{max} $ integers — the positions of the elements from the optimal subsequence in the ascending order. Note that you can find and print any subsequence with the maximum length.

输入输出样例

输入样例 #1

7 8
6 2 9 2 7 2 3

输出样例 #1

6 5
1 2 4 6 7

输入样例 #2

6 4
2 2 2 3 3 3

输出样例 #2

2 3
1 2 3

题意翻译

给出n个数，要求选出尽可能多的数，满足它们的最小公倍数不大于m。允许数列里没数，此时这个数列的最小公倍数为1。 $n,m<={10}^{6}$ $a_i <= {10}^{9} $ 感谢@fs6y 提供的翻译