НОД Чисел в наборе

@Reshaldo · Регистрация: 23.02.2023

Студворк — интернет-сервис помощи студентам

Здравствуйте
В первой строке записано целое число q (1<=q<=10e+5) — количество операций с набором. Каждая из следующих q строк имеет вид «+ x» или «- x». В первом случае число x добавляется в набор, а во втором случае — удаляется из него. Число x целое, положительное и не превосходит 10e+9. Гарантируется, что из набора будут удаляться только числа, которые в нём лежат.
Нужно вывести НОД всех чисел в наборе, после каждой операции,наибольшим общим делителем пустого набора является единица.

@Red white socks · 12.04.2023, 19:27

Reshaldo, в чем проблема?

@eaa · 12.04.2023, 19:31

Reshaldo, НОД ассоциативная операция?

@Reshaldo · 12.04.2023, 19:33 **[ТС]**

Red white socks, Конкретно интересует как находить НОД, у чисел например в list, например есть набор 26 39 52, нод 13, но как его найти?

Добавлено через 1 минуту
eaa, Скорее всего нет, надо ко всем набору сразу

@Red white socks · 12.04.2023, 19:41

Reshaldo, лучшим алгоритмом на Земле - алгоритмом Евклида

eaa, я вижу проблему, мне важно, чтобы ТС ее опознал и по полочкам разложил.

Добавлено через 1 минуту

Сообщение от Reshaldo

eaa, Скорее всего нет, надо ко всем набору сразу

Пальцем в небо? А если подумать? А если это подсказка?

@eaa · 12.04.2023, 19:47

Red white socks, это я еще про коммутативность не спросил)))

@Reshaldo · 12.04.2023, 19:51 **[ТС]**

Red white socks, В задании не сказано, но если сам НОД ассоциативен,я могу запоминать его и сравнивать с новым добавленным числом, но как тогда поступить когда число удаляется из набора?

@eaa · 12.04.2023, 19:53

Python
1
2
3
4
5
6
7
8
9
10
from math import gcd
a = []
for _ in range(int(input())):
    cmd, *x, = input().split()
    x = int(x[0])
    if cmd == '+':
        a.append(x)
    else:
        a.remove(x)
    print(gcd(*a))

Добавлено через 1 минуту
но это не решит проблему при больших q.

@Reshaldo · 12.04.2023, 19:55 **[ТС]**

eaa, Спасибо

@eaa · 13.04.2023, 07:24

Не по теме:

Red white socks, ну вот даже в лес не пришлось идти деревья рубить)

@Red white socks · 13.04.2023, 08:31

Сообщение от Reshaldo

но как тогда поступить когда число удаляется из набора?

Спасибо, что озвучили проблему. Да, при удалении нужно пересчитывать для всех чисел. Жаль, что удовлетворены лобовым подсчетом, но возможно вы сами додумались, как уменьшить квадратичную асимптотику.

Не по теме:

eaa, у меня, если честно, только сожаления по этому поводу.

Добавлено через 7 минут
eaa, а может и не было никакой проблемы? Если на случайных числах, то там быстро до единицы скатывается и предложенный алгоритм условно линеен по числу чисел?

@eaa · 13.04.2023, 08:34

Red white socks, в любом случае TLE будет на таких ограничениях.

@Aviz__ · 13.04.2023, 08:40

Не по теме:

Сообщение от Red white socks

мне важно, чтобы ТС

достойные слова, не равнодушного человека! но тут ты скорее заработаешь инфаркт, чем расшевелишь спящий ум((.

@Red white socks · 13.04.2023, 09:15

eaa, ну да, из-за удалений из списка. А НОД и не при делах.

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! в-строка - входное арифметическое выражение в инфиксной(обычной). . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@Reshaldo 0 / 0 / 0 Регистрация: 23.02.2023 Сообщений: 53

	НОД Чисел в наборе 12.04.2023, 19:03. Показов 902. Ответов 13 Метки нет (Все метки) Здравствуйте В первой строке записано целое число q (1<=q<=10e+5) — количество операций с набором. Каждая из следующих q строк имеет вид «+ x» или «- x». В первом случае число x добавляется в набор, а во втором случае — удаляется из него. Число x целое, положительное и не превосходит 10e+9. Гарантируется, что из набора будут удаляться только числа, которые в нём лежат. Нужно вывести НОД всех чисел в наборе, после каждой операции,наибольшим общим делителем пустого набора является единица. 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	12.04.2023, 19:27
	Reshaldo, в чем проблема? 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	12.04.2023, 19:31
	Reshaldo, НОД ассоциативная операция? 0

@Reshaldo 0 / 0 / 0 Регистрация: 23.02.2023 Сообщений: 53
	12.04.2023, 19:33 [ТС]
	Red white socks, Конкретно интересует как находить НОД, у чисел например в list, например есть набор 26 39 52, нод 13, но как его найти? Добавлено через 1 минуту eaa, Скорее всего нет, надо ко всем набору сразу 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	12.04.2023, 19:47
	Red white socks, это я еще про коммутативность не спросил))) 0

@Reshaldo 0 / 0 / 0 Регистрация: 23.02.2023 Сообщений: 53
	12.04.2023, 19:51 [ТС]
	Red white socks, В задании не сказано, но если сам НОД ассоциативен,я могу запоминать его и сравнивать с новым добавленным числом, но как тогда поступить когда число удаляется из набора? 0

@Reshaldo 0 / 0 / 0 Регистрация: 23.02.2023 Сообщений: 53
	12.04.2023, 19:55 [ТС]
	eaa, Спасибо 0

@eaa
	13.04.2023, 07:24
	Не по теме: Red white socks, ну вот даже в лес не пришлось идти деревья рубить) 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	13.04.2023, 08:34
	Red white socks, в любом случае TLE будет на таких ограничениях. 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	13.04.2023, 09:15
	eaa, ну да, из-за удалений из списка. А НОД и не при делах. 0

НОД Чисел в наборе

Решение