Помогите решить задачу "Лампочки"!

Имеется следующая задачка:

Имеется ряд из N лампочек, которые пронумерованы от 1 до N. Изначально ни одна из лампочек не горит. Далее происходит K последовательных линейных инверсий этого ряда ламп. Под линейной инверсией понимается инверсия каждой P-й лампочки в ряде. Например, если P=3, то произойдет инверсия 3й, 6й, 9й и т.д. лампочек.

Требуется определить: сколько горящих лампочек останется после реализации всех заданных линейных инверсий?

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

В первой строке входного файла INPUT.TXT заданны числа N и K – число лампочек и число линейных инверсий. Вторая строка состоит из K целых чисел Pi, задающих период данных инверсий. (1 <= N <= 10^9, 1<=K<=100, 1 <= Pi <= 50)


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

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

У кого какие мысли пишите!!!!

Как говорил препод у нас в инсте - "Ну, чтобы до сердца дошло - пример". Пример - ...отсутствует. Посему буду считать что условие понял верно.
Пишем алгоритм:

Есть массив - А, размер 10^9 (зависит от N), инициализируем нулями (положение выкл)
Есть масиив - Б, размер 100 (зависит от K)

Считываем данные, заполняем массив Б (элементами Pi).

Обработка происходит в двойном цикле. Внешний цикл - от 0 до K, шаг 1; внутренний от 0 до N, шаг Б[K].
В теле цикла инвертируем значение А[счетчик внутреннего цикла].

Усе.

Ну это тупой вариант, как грится - в лоб.
Если похитрее - для начала можно обработать массив Б. Если в нем встречаются два одинаковых значения(в условии не сказано, что такого не может быть) то их можно "сократить".

Очевидные вещи (навскидку):
- Лампа горит, если количество "инверсий" нечетно;
- Парные инверсии можно отбросить;
- Период конечного состояния = НОК(Р).

Из любопытства посчитал - масимально возможный период = 619808900849199341280

PS. Обработка массива из 10^9 элементов (даже битовых) - это, я вам скажу... однако поскольку количество элементов намного меньше максимального периода - задачка сильно смахивает на переборную.

Сообщение отредактировано: Akina - 23.09.08, 15:20

Суровые условия.

Слишком большое N не позволяет решить задачу "в лоб" (для хранения всего ряда потребуется около 120 МБ памяти). Слишком большое K затрудняет использование методов вроде "выбрать все числа, делящиеся на P или Q, но не на P и Q одновременно" (слишком много таких условий, легко запутаться). Большой диапазон P не позволяет (в общем случае) выделить наименьшее общее кратное и разбить ряд на меньшие периоды (это самое НОК намного больше N).

Я сталкивался с похожей проблемой при построении бесконечного (точнее, очень длинного) ряда простых чисел методом "решето Эратосфена". Решение заключается в том, чтобы разбить длинный ряд на короткие блоки, обрабатывать каждый блок отдельно, и для каждого числа P[i] запоминать номер первого элемента в следующем блоке, который нужно будет инвертировать. Когда очередной блок обработан (применены все инверсии), считаем количество включенных элементов и добавляем его к общей сумме.

Пусть мы разбили ряд на блоки длиной M элементов (M невелико), блоки и элементы в блоке нумеруются с единицы. Для каждого числа P[i] и для каждого блока определен номер первого инвертируемого элемента - S[i, j], где j - номер блока. S[i, 1] = P[i], S[i, j] = P[i] - (M - S[i, j-1]) mod P[i], где mod - остаток от целочисленного деления. Изначально все элементы в блоке выключены. Для каждого числа P[i] инвертируем каждый P[i]-ый элемент, начиная с S[i, j]-ого, и вычисляем следующее значение S. Когда все инверсии для всех P[i] сделаны, считаем включенные элементы и переходим к следующему блоку.

Пример: M = 100, P[i] = 13, S[i, 1] = P[i] = 13. Инвертируем 7 элементов, вычисляем S[i, 2] = P[i] - (M - S[i, 1]) mod P[i] = 13 - (100 - 13) mod 13 = 13 - 9 = 4 (во втором блоке начинаем инверсию с четвертого элемента).

Прежде, чем начинать работу, желательно учесть следующее: если среди P[i] встречается (2*n) одинаковых чисел, конечный эффект будет такой же, как если бы этих чисел вообще не было; если встречается (2*n + 1) одинаковых чисел, эффект такой же, как если бы было только одно такое число.

Блин, свел задачу к уже решенной - как математик из анекдота :( А все решается намного проще и без лишнего расхода памяти.

Перебираем числа L от 1 до N, для каждого P[i] храним "расстояние" до следующего кратного числа (для единицы это "расстояние" равно P[i] - 1). При переходе к следующему L уменьшаем эти "расстояния" на единицу. Если для какого-то P[i] "расстояние" уменьшилось до 0 - помечаем L как кратное P[i] и в "расстояние" записываем P[i]. Считаем количество P[i], для которых L является кратным. Если это количество нечетное - лампочка горит, если четное - не горит.

Цитата AVA12 @ 23.09.08, 17:14

Перебираем числа L от 1 до N

То есть полный перебор.

Хм, действительно перебор какой-то (или я алгоритм не понял )... Но как-то это слишком медленно получается если нам требуется число действий пропорциональное N.

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

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


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

Цитата albom @ 23.09.08, 19:42

Работает довольно быстро

Если не считать, что количество групп НОКов = 2^k-1... если останется полсотни периодов, то лучше прямой перебор

Цитата Akina @ 23.09.08, 20:41

Если не считать, что количество групп НОКов = 2^k-1...

Пост мой весь прочитал или нет?
Да, всего групп 2^K, но почти все они нулевые и мы их умеем эффективно отсекать.

Цитата Akina @ 23.09.08, 20:41

если останется полсотни периодов, то лучше прямой перебор

Время работы на наихудшем тесте при указанных ограничениях на входные данные я привел, думаешь полный перебор справится за такое же время?

А трудоемкость подсчета 2^k НОКов ?
Они не нулевые, а больше N, но их же надо посчитать??

Да уж, помоему ( ) все приведённые варианты имеют большую трудоемкость, чем прямой перебор. Вижу вариант в упрощении массива чмсел Pi. Кстати, по условию K < 100, но Pi < 50. Так что если K будет больше 50, значит будут повторения, которые сократяться. Можно дальше упрощать. Скажем, преобразовать массив Рi в матрицу. Где первое значение это шаг, а второе это сдвиг. Таким образом пара чисел у которых НОД равен одному числу, сократятся до одного числа, а сдвиг потом будет учтен по расчете.

Цитата _lcf_ @ 23.09.08, 21:30

Они не нулевые, а больше N, но их же надо посчитать??

Да не нужно их считать! Прямо же написал и даже выделил курсивом Идею При ее применении НОКи мрут как мухи

Цитата _lcf_ @ 23.09.08, 21:30

все приведённые варианты имеют большую трудоемкость, чем прямой перебор.

Ты не прав

Добавлено 23.09.08, 21:39
Вот тебе числа при N=10^9, K=50, числа P_i разные:
количество посчитаных НОК от общего числа: 0.0000000256%
максимальный размер таблицы M: 38k элементов

albom может объяснишь попроще, как отображение М помогает искать НОКи большие N...

Цитата _lcf_ @ 23.09.08, 21:49

как отображение М помогает искать НОКи большие N...

Нам не нужны НОКи больше N, так как они не дадут вклада в ответ (первая загоревшаяся лампочка при такой комбинации отстоит от начала на расстояние больше чем N).

Ваще не берусь никак судить.
С отображением я все понял. Дальше:

Цитата albom @ 23.09.08, 21:32

количество посчитаных НОК от общего числа: 0.0000000256%
максимальный размер таблицы M: 38k элементов

Я бы сказал имеено так - посчитано 38 тыщ НОКов. Модуль 10^9. Какая таки трудоемкость? Или ты знаешь какой-то хитрый способ поиска НОКов?

Добавлено 23.09.08, 22:30
здесь была чушь

Сообщение отредактировано: _lcf_ - 23.09.08, 22:33

Цитата _lcf_ @ 23.09.08, 22:23

Я бы сказал имеено так - посчитано 38 тыщ НОКов.

38k - размер таблицы M, НОКов счиатается больше, так как они довольно часто совпадают, и из них примерно каждый четвертый посчитаный НОК не попадает в таблицу, т.к. оказывается больше N.

Цитата _lcf_ @ 23.09.08, 22:23

Какая таки трудоемкость? Или ты знаешь какой-то хитрый способ поиска НОКов?

Трудоемкость поиска НОК? Ну первый аргумент у НОК всегда число P_i, так что можно сделать препроцессинг и считать весьма быстро, хотя достаточно считать просто НОК(a,b) = a * b / НОД(a, b), а НОД уже обычным алгоритмом Евклида.