V🇺
k * gcd всех?
🤔
Size: a a a
2020 October 13
A
а может не быть взаимно простым, тогда gcd
A
так что наверно gcd всех, в том числе модуля
AD
модуль это же abs а не mod?
A
мод видимо
ЕВ
Если вы про условие
ЕВ
Исправил - вставляем во множество модуль разницы для пары.
A
а, то есть мы берем пару чисел и добавляем их разницу (которая не превосходит их самих)
ЕВ
а, то есть мы берем пару чисел и добавляем их разницу (которая не превосходит их самих)
Да
A
но все равно выглядит как gcd
A
потому что если у нас есть два произвольных a и b, то методом эвклида мы получим и их gcd
V🇺
Ребят, привет всем. Хотел бы услышать идеи на решение такой задачи.
Есть множество с положительными целыми числами по модулю до 10^9, количество до 10^6.
Над множеством нужно делать следующие действия, пока оно будет изменяться: берём все возможные пары из различных чисел и вставляем в это множество модуль их разницы.
После этого нужно найти k-th largest.
Как это можно сделать эффективно?
Есть множество с положительными целыми числами по модулю до 10^9, количество до 10^6.
Над множеством нужно делать следующие действия, пока оно будет изменяться: берём все возможные пары из различных чисел и вставляем в это множество модуль их разницы.
После этого нужно найти k-th largest.
Как это можно сделать эффективно?
пары из двух одинаковых тоже рассматриваем?
ЕВ
пары из двух одинаковых тоже рассматриваем?
Нет
A
ну разве что нуля мы не получим
V🇺
если нет, то кажется что множество гарантированно рано или поздно опустеет
A
множество не уменьшается
V🇺
потому что max-min строго убывает после каждой итерации
A
оно только растет
ЕВ
оно только растет
+