@ilya-punk

Лампочки
(Время: 2 сек. Память: 16 Мб Сложность: 94%)
Имеется ряд из 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)

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

В выходной файл OUTPUT.TXT следует вывести ответ на задачу.

Долго ломал голову. Нашёл вот этот пост ссылка удалена
Но толком не понял, какая формула для произвольного N подразумевается, и как отсекаются лишние слагаемые?

	Комментарий модератора
	Ссылки на сторонние форумы запрещены

Добавлено через 19 минут
Поскольку ссыль удалили, вот то сообщение
Берем первое число P1, тогда после применения будут гореть N/P1 лампочек (тут и далее подразумевается округление вниз).
Берем второе число P2, после второй инверсии будут гореть N/P1 + N/P2 - N/НОК(P1, P2) * 2 ламочек (поясню, мы считаем сколько зажигает лампочек каждая инверсия поотдельности и вычитаем из них кол-во лампочек, зажженных обоими).
Для трех инверсий: N/P1 + N/P2 + N/P3 - N/НОК(P1, P2) * 2 - N/НОК(P1, P3) * 2 - N/НОК(P2, P3) * 2 + N/НОК(P1, P2, P3) * 4.
И так далее. По индукции всё получается довольно просто.

Вот только при наивном подходе у нас в сумме будет 2^K слагаемых, что, вообще говоря, отрицательно сказывается на производительности. Но функция НОК растет довольно быстро (хоть у нее и более одного аргумента, но, думаю, понято, что я имею ввиду), и поэтому большинство слагаемых будут равны нулю! Поэтому применяем идею: как только HOK(...) превышает N, то это слагаемое и все последующие в которых учавствуют теже аргуменеты (+плюс какие-то другие) можно не считать.
Осталось научится быстро определять такие нулевые слагаемые.
Для этого заводим отображение M: p -> i, где p - инверсия, i - коэффициент перед слагаемым в сумме.
Изначально M пусто, и для каждого k (1 <= k <= K) добавляем в M пару (Pk -> 1) и обновляем отображения для всех элементов M - то есть добаляем пару (НОК(Pk, pj) -> -2*ij), где (pj -> ij) - уже существующая пара в M.

Пример, если у нас N=100, и на вход пришли числа 3, 4, 5, 8 то M будет эволюционировать так:
k = 0:

p

i

k = 1:

p	i
3	1

k = 2:

p	i
3	1
4	1
12	-2

k = 3:

p	i
3	1
4	1
12	-2
5	1
15	-2
20	-2
60	4

k = 4:

p	i
3	1
4	1
12	-2
5	1
15	-2
20	-2
60	4
8	-1
24	2
40	2
120	-

120 не вошло в M, т.к. N < 120

Все, теперь, когда у нас M построено, то кол-во лампочек считается элементарно:
Sum_{k \in M}( (N / pk) * ik)


Работает довольно быстро (при тупой реализации в худшем случае - одна десятая секунды), памяти практически не нужно (ну пара сотен килобайт - максимум) (лень сейчас получать оценки сложности, кому интересно - посчитайте).
Единственно, очевидную оптимизации в виде удаления пар одинаковых чисел на входе лучше тоже сделать, хотя и без нее не сильно медленее получается.

Добавлено через 1 минуту
Надеюсь, админы меня не покарают

0