Олимпиадная задачка - найти K минимально близкое ( разницей сумм делителей + разность самих чисел) к заданному числу N - Паскаль, Turbo Pascal, PascalABC.NET - Страница 4

Poma][a · 19.03.2015, 17:44

Дык это-то понятно.. именно время и интересовало.. Спасибо!

Аватар · 20.03.2015, 09:37

Оптимизировал SumDel вообще летать стало 10^7 чуть больше секунды

Код:

function SumDel(ak: Integer): Integer;
var ti,tk: Integer;
begin
  tk:=Trunc(Sqrt(ak)+0.1);
  if tk*tk>ak then Dec(tk);
  Result:=1;
  for ti:=2 to tk-1 do if ak mod ti=0 then Inc(Result,ti+(ak div ti));
  if ak mod tk=0 then Inc(Result,tk);
end;

Serge_Bliznykov · 20.03.2015, 10:01

Цитата:

Сообщение от Аватар

Оптимизировал SumDel вообще летать стало 10^7 чуть больше секунды

Код:

function SumDel(ak: Integer): Integer;
....

Красотища! Примите мой респект!!
грущу, что не смог до этого дойти своим умом..

Poma][a · 11.07.2015, 16:43

Ночевать пришлось вместе без интернета - вспомнил эту задачу..
А что если разложить число на множители :
900 = 2*2*3*3*5*5 (их не больше log2(n))
Прекрасно. Теперь делаем такую красоту :
бежим по этим множителям, ища их произведение :

Получаем алгоритм, который на k-ом шаге берет произведение k первых множителей. А дальше у нас будет массив простых чисел (их 664579 (до 10^7)) и там бинарным поиском ищем число больше нашего и меньше нашего (но ближайщие к полученному). А дальше эти два умножаем на оставшиеся. Получаем (log2(n))^2 * (18)
Летать будет, не?

Правда нужно сохранить эти 664579 числа.. А это 4 байта на брата итого 2мб.. сойдет, не?

20.03.2015, 09:37	#32
Аватар Старожил Регистрация: 17.11.2010 Сообщений: 18,922	Оптимизировал SumDel вообще летать стало 10^7 чуть больше секунды Код: `function SumDel(ak: Integer): Integer; var ti,tk: Integer; begin tk:=Trunc(Sqrt(ak)+0.1); if tk*tk>ak then Dec(tk); Result:=1; for ti:=2 to tk-1 do if ak mod ti=0 then Inc(Result,ti+(ak div ti)); if ak mod tk=0 then Inc(Result,tk); end;` Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Вычислить произведение чисел, неравных заданному числу Z	Hug	Помощь студентам	4	12.11.2013 23:27
найти кол-во трехзначных чисел сумма простых делителей которых кратна 5 (на Делфи)	anzorchik	Помощь студентам	2	02.10.2011 16:18
Определить ближайший элемент массива к заданному числу	wowan	Паскаль, Turbo Pascal, PascalABC.NET	1	28.05.2011 23:21

19.03.2015, 17:44	#31
Poma][a Новичок Джуниор Регистрация: 11.10.2011 Сообщений: 3,882	Дык это-то понятно.. именно время и интересовало.. Спасибо!

11.07.2015, 16:43	#34
Poma][a Новичок Джуниор Регистрация: 11.10.2011 Сообщений: 3,882	Ночевать пришлось вместе без интернета - вспомнил эту задачу.. А что если разложить число на множители : 900 = 223355 (их не больше log2(n)) Прекрасно. Теперь делаем такую красоту : бежим по этим множителям, ища их произведение : Получаем алгоритм, который на k-ом шаге берет произведение k первых множителей. А дальше у нас будет массив простых чисел (их 664579 (до 10^7)) и там бинарным поиском ищем число больше нашего и меньше нашего (но ближайщие к полученному). А дальше эти два умножаем на оставшиеся. Получаем (log2(n))^2 (18) Летать будет, не? Правда нужно сохранить эти 664579 числа.. А это 4 байта на брата итого 2мб.. сойдет, не?