← 返回题目

题库练习 Longest Subsequence

← 上一题下一题 →

A10360 | $Longest Subsequence$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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

C++ 编辑器

输入

输出