Имеется ряд из N лампочек, которые пронумерованы от 1 до N. Изначально ни одна из лампочек не горит. Далее происходит K последовательных линейных инверсий этого ряда ламп. Под линейной инверсией понимается инверсия каждой P-й лампочки в ряде. Например, если P=3, то произойдет инверсия 3й, 6й, 9й и т.д. лампочек.
Требуется определить: сколько горящих лампочек останется после реализации всех заданных линейных инверсий?
Объясните пожалуйста, как решить данную задачу?
Ограничения в студию
В первой строке входного файла INPUT.TXT заданны числа N и K – число лампочек и число линейных инверсий. Вторая строка состоит из K целых чисел Pi, задающих период данных инверсий. (1 <= N <= 109, 1<=K<=100, 1 <= Pi <= 50)
Тынц
Задача
Решается методом включений-исключений.
Можно поискать ее обсуждение в сети, решение есть, например, здесь
Забавно, как описание albom-a из моей ссылки расползлось по интернету :)
Спасибо большое за помощь :)
Этот алгоритм дает TL.
Нет, не дает. НОК-ов надо рассматривать не 2^N, а гораздо меньше.
А по подробнее можно.
Что именно поподробнее? Было две ссылки, в первой было обсуждение, в котором у участников тоже возникали сомнения в скорости алгоритма. Я же вряд-ли смогу расписать понятнее, чем написано там :)
[Вот моя задача] На 8 тесте TL или я не оптимизирую решения. (http://pastebin.com/4mGUUha1)
При таких вычислениях некоторые НОК-и ты будешь считать несколько раз. Можно попробовать оптимизировать, сортируя после каждого добавления НОК-и (внутри цикла до m) и объединяя одинаковые. Но лучше переписать это на другом языке (например, С++) с использованием ассоциативных массивов (map).
ИМХО, проще свой хешмап написать
Думаю, не проще переписывания на другой язык :)