eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Дельфины

Дельфины

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Весна… Крилики радуются солнышку, небо стало добрым и мягким, появились первые цветочки, дельфины прилетели из тёплых краёв.

Действительно! Дельфины - главный символ весны для криликов. Ведь они так красиво поют, летают, кружатся. Такое поведение дельфинов приносит радость и улыбки почти всем, почти… Учёным криликам из Института контроля популяции дельфинов в верхушках деревьев Криляндии радостная пора приносит уймй работы. Им нужно контролировать целые стаи дельфинов. Но они не расстраиваются, потому что нашли на кого повесить самую нудную работу - разработку алгоритма для предсказания популяции дельфинов в верхушках деревьев.

Итак, нужно написать программу, которая определяет вероятные позиции дельфинов. Изначально будет дано описание N дельфинов.Всего следует проследить за M деревьями. Каждый дельфин изначально сидит на верхушке какого-то дерева. Каждый дельфин в течении одной секунды может с равной вероятностью перелететь на любое дерево с номером взаимно простым с номером того дерева, на котором сидит дельфин (т.е. таким, что наибольший общий делитель раівен 1), либо остаться на том де дереве. То есть, если деревьев 6, и дельфин сидит на дереве под номером 3, то события "дельфин через секунду окажется на дереве под номером1 (или 2, 3, 4, 5)" – равновероятны.

Для проверки того, что Ваш алгоритм правильный, виведитеь сумму математических ожиданий количества дельфинов на деревьях (через T секунд). То есть, если m_1, m_2, ..., m_M – математичнеские ожидания количества дельфинов соответственно на первом, втором, ..., M-м дереве, то нужно вычислить

Входные данные

Первая строка содержит три целых числа, разделённых пробелами: N, M, T (1M, N, T1000) – количество дельфинов, количество деревьев и время, которое нужно промоделировать. Вторая строка содержит N целых чисел, разделённых пробелами, соответственно начальные расположения дельфинов (деревья нумеруются числами от 1 до M).

Выходные данные

В единственной строке вывести результат вычислений с двумя знаками после запятой.

Пример

Входные данные #1
1 1 1
1
Выходные данные #1
1.00
Источник ACM-ICPC Ukraine 2012, 1st Stage Ukraine, April 21, 2012