Как реализовать прибавление на отрезке, для нахождения НОД за loglog. Я понял как сделать прибавление для нахождения суммы но не могу понять как реализовать это
Хранишь НОД всех разниц на отрезке и любой элемент отрезка в вершине ДО. А тебе это точно нужно?
я хотел узнать можно ли решить эту задачку за счет ДО
Задача A. Баука и Гора Великих Чисел
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Баука любит прогуливаться по утрам, из-за этого с восходом солнца он пошел на гору Великих
Чисел. С собой он взял любимый массив из N элементов, где i-е число равно ai
. Баука хочет найти
великое число для своего массива.
Число x считается великим, если для него выполняется такое условие, что НОД(ai+x, aj +x) = 1
для всех 1 6 i < j 6 N.
Числа на горе представлены в виде Q запросов. В каждом запросе дается одно число. Помогите
Бауке определить, будет ли данное число великим для его массива.
Формат входных данных
В первой строке находятся два целых числа N и Q (2 6 N 6 105
, 1 6 Q 6 104
) - количество
чисел и запросов.
Во второй строке находятся N целых числа a1, a2, · · · , an (1 6 ai 6 105
).
В следующих Q строках дано по одному целому числу x (1 6 x 6 105
).
Формат выходных данных
На каждый из Q запросов выведите «YES», если число является великим, иначе выведите «NO».
Допустим ты сможешь поддерживать такую структуру данных, как она тебе поможет решать эту задачу?
К сожалению, с помощью простой ДОшки эту задачу нельзя решить 
Но как я помню, один из всероссников говорил, что ее можно сдать FFT + Персис ДО, но это лютый гемор. Задача имеет гораздо легче решение, без всяких структур данных
Лучше создай новую тему с конкретно этой задачей.
1 лайк
зачем, эта тема и так посвящена задаче же
Да, но ДОшкой и прибавлением на отрезке с НОДом эту задачу никак не решить
Вот сюрприз будет новичкам, открывают тему про ДО, а там в итоге решение задачи, где кроме Решета Эратосфена из алгосов/структурок ничего не используется
ты про что?
1 лайк
Про Ашку с области)
Я просто написал одному всеросснику и он сначала решение на 70 баллов написал(оно было нормальное, по модулям рассматривал), а потом про какую-то лютую Персис ДОшку с FFT и сказал, что это должно заходить на 100. Это было касаемо решения, где хоть как-то ДОшка используется. Мб есть и другое…
Если FFT использовать то можно же тогда просто GCD convolution считать.
UPD. А нет, но может быть он и использовал GCD convolution
UPD2. Ариф, я тебе дал свой акк, чтобы поддерживать streak, а не отвечать на вопросы))
2 лайка
Я уже подумал когда ты успел стать информатиком
2 лайка