K
Не евклид тоже не сдавался
Size: a a a
2021 May 05
DK
Ладно, благодарю. Попробую пойти напрямую через Евклида (пишу на плюсах). Мб даже прокатит, но это вряд ли
p
Может, на джаве?
PO
Массив не изменяется - однократный проход за O(n * log(max)), изменяется - факторизация и считаешь аккуратненько где у тебя количество вхождений равно количеству чисел, за O(n*sqrt(max))
K
там было ограничение что все возможные числа меньше 10000, ну и простой предобсчёт - храним для 3000*3000 и факторизации для больших чисел
p
Для статичного за O(n) работает
PO
При n >= log(max), да, в принципе
K
там на выбор java и python
PO
Чет туплю
p
При n>log2(1e18)
K
и на джаве ограничение на время злое
PO
А для изменяющегося можно и до херакнуть, в принципе
PO
Тогда O(nlog(n)) будет с log(n) + log(max) на запрос
PO
Может там распараллеливать надо было?
K
нет, одно ядро
K
был другой алгоритм, который сдавался чуть проще
PO
Тогда мб надо было найти минимальное число сначала как вариант?
PO
Хотя вроде не должно давать выигрыша
K
не, там именно куча вызовов gcd от довольно произвольных пар