eolymp
bolt
Try our new interface for solving problems
Məsələlər

Произведение чисел

Произведение чисел

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 122 MiB

Заданы целые числа A[1], A[2], ..., A[n] и число m.

Выберите такое подмножество чисел A[1], A[2], ..., A[n], чтобы их произведение, взятое по модулю m, было максимально.

Giriş verilənləri

В первой строке заданы два целых числа n и m (1n100, 1m10000). Во второй строке записаны n целых чисел A[1], A[2], ..., A[n] (0A[i]10000).

Çıxış verilənləri

В первой строке выведите числа p и k - произведение выбранных чисел по модулю m и количество выбранных чисел, соответственно. Во второй строке выведите k чисел B[1], B[2], ..., B[k] - номера выбранных чисел. Номера должны быть попарно различны. Если ответов с максимальным p несколько, можно выводить любой из них.

Nümunə

Giriş verilənləri #1
3 5
1 2 3
Çıxış verilənləri #1
3 2
3 1
Giriş verilənləri #2
5 8
5 4 3 2 1
Çıxış verilənləri #2
7 3
5 3 1
Müəllif Ivan Kazmenko
Mənbə Lisiy Nos Training on Dynamic Programming, Part 1