Codeforces Round 365 (Div. 2) |
---|
Закончено |
Вдоволь наигравшись со своим красивым массивом, Мишка решила углубиться в изучение математики. Научившись умножать и делить и изучив понятие кратности, она заинтересовалась следующей задачей.
Дано целое число k и массив целых чисел a1, a2, ..., an длины n. Необходимо найти такую непустую подпоследовательность элементов заданного массива, что произведение её элементов кратно k, а её размер минимален.
Формально, требуется найти последовательность индексов 1 ≤ i1 < i2 < ... < im ≤ n, такую, что делится на k, а m принимает наименьшее возможное значение.
Если же существует несколько таких подпоследовательностей, то следует выбрать ту из них, сумма элементов которой минимальна.
Мишка быстро справилась с этой задачей. А сможете ли Вы?
В первой строке входных данных содержатся два целых числа n и k (1 ≤ n ≤ 1 000, 1 ≤ k ≤ 1012).
Во второй строке входных данных содержатся n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 1012) — элементы массива.
В первой строке выведите целое положительное число — количество элементов в искомой подпоследовательности.
Во второй строке выведите m различных целых чисел — последовательность индексов элементов исходного массива, входящих в искомую подпоследовательность.
Если искомых последовательностей несколько (то есть подпоследовательностей из наименьшего количества элементов с минимально возможной суммой элементов), то разрешается вывести любую из них.
Если таких последовательностей не существует, выведите - 1 в единственной строке.
5 60
2 4 6 5 2
3
4 3 1
Название |
---|