Alexandroppolus, можно и с О(sqrt(5000)) памяти. Сначала решетом найти для всех чисел до корня минимальный простой делитель. А потом искать gcd сливая списки простых. Если аккуратно подсчитать сколько там суммарно простых делителей среди всех чисел - будет линия.
Alexandroppolus, Я тоже сначала подумал про ответ за O(1). Даже какие-то формулы пытался выводить. Но там все не так просто, потому что надо, чтобы GCD(n,m) == 1, иначе тройки перебираются с повторами. Если и есть какая-то замкнутая формула, то там какой-нибудь ужас вроде дзетта-функции римана.
Даже не надо их генерировать. Достаточно перебрать n и m, найти k максимально возможное (поделив 5000 на c), прибавить к счетчику k. На максимум проверять надо 2km(m+n). У этого решения будет линейная сложность относительно ограничения на размер чисел.
asdsdsdafsdafdsaf, да, похоже на правду. Вот тут есть вообще код. Только его можно еще соптимизировать. Не надо копировать результат в начальный массив - лучше пусть функция принимает два вектора одинакового размера и по какому разряду надо сортировать. А дальше вызывайте ее перекладывая данные из одного вектора в другой и назад. Для этого удобно завести массив из двух векторов и класть из i%2 в (i+1)%2.
asdsdsdafsdafdsaf, неееет! Зачем там списки! Нужен лишь один вектор размера с сортируемый. За один проход в массиве на 256/65536 элементов считаете, сколько раз данная цифра в текущем разряде встречается. Потом за один проход пересчитываете, сколько чисел содержат меньшие данной цифру. Это будут индексы отрезков в результирующем массиве, куда надо поместить все числа с данной цифрой. Потом за второй проход все числа перемещает, увеличивая эти индексы.
Нет, этот изврат с генерированием псевдослучайной последовательности сделан, чтобы бороться с дико медленным вводом, который на разных языках и разными методами будет работать в разы медленнее или быстрее. Просто физически невозможно подобрать ограничения в задаче, которые бы надежно отсекали действительно быструю сортировку от не очень оптимальной, если 95% времени работы программы - ввод.
Метод генерации псевдослучайный как раз, чтобы шибко умные не придумали такую формулу.
asdsdsdafsdafdsaf, Хм... память под последовательность аккуратно один раз выделяете (capacity или resize у вектора)? Если все-равно не проходит, то, наверно, придется писать какой-нибудь radix sort. Естественно, сортировать надо не по десятичным цифрам, а, допустим, по байтам. Или по 4 бита в разряде.
asdsdsdafsdafdsaf, Ну, делать merge по мере генерации - это почти гарантированно O(N^2). Там надо очень сильно извратиться, чтобы логарифм в итоге получить.
asdsdsdafsdafdsaf, Посмотрел ограничения - удивился. Что, встроенная в язык сортировка (например std::sort в C++) не проходит? Ваша реализация merge sort наверняка далеко не оптимальна.
pshevnin, Ну тогда, да, ваш подход будет работать. Просто увеличивайте массив, чтобы все индексы существовали. Не забудьте через memset затереть новую область нулями.
