[Dmitry_DM]

Здравствуйте! Обращаюсь к знатокам. Есть задача "По заданному натуральному числу N необходимо вычислить количество натуральных чисел, которые являются делителями N! (факториала числа N)."
Доп. условие: лимит времени 1с.
Но у меня не проходит несколько тестов из-за исчерпанного лимита времени. Как можно оптимизировать?

Код:

var fack:Int64;
 i,n,k:Integer;
 begin
 fack:=1;
 Readln(n);
for i:=2 to n do
 fack:=fack*i;

for i:=1 to fack do
if fack mod i=0 then inc(k);
 Writeln(k);
 end.

[M.A.D.M.A.N.]

Код:

var fack:Int64;
 i,n,k:Integer;
 begin
 fack:=1;
 Readln(n);
asm
  cli
end
for i:=2 to n do
 fack:=fack*i;
 
for i:=1 to fack do
if fack mod i=0 then inc(k);
asm
  sti
end
 Writeln(k);
 end.

[Dmitry_DM]

Сообщение от M.A.D.M.A.N.

Код:

var fack:Int64;
 i,n,k:Integer;
 begin
 fack:=1;
 Readln(n);
asm
  cli
end
for i:=2 to n do
 fack:=fack*i;
 
for i:=1 to fack do
if fack mod i=0 then inc(k);
asm
  sti
end
 Writeln(k);
 end.

А это вообще на delphi Consol Application работает? У меня пишет, что странный код:

Код:

asm

и запускается только если добавить ; после end здесь

Код:

asm
  cli
end

что это?

Код:

cli

Код:

sti

Но при выполнении что-то очень быстро выдает, но не ответ.

[Aristarh Dark]

M.A.D.M.A.N., а не наоборот?

Dmitry_DM, во втором цикле достаточно to fack div 2 do

[M.A.D.M.A.N.]

Сообщение от Aristarh Dark

M.A.D.M.A.N., а не наоборот?

Именно в такой последовательности "Clear Interrupt-Enable Flag" и "Set Interrupt-Enable Flag".

В принципе второй цикл можно затолкать в первый.

Типа:

Код:

var fack:Int64;
 i, j,n,k:Integer;
 begin
 fack:=1;
 Readln(n);
for i:=2 to n do
begin
 for j := fack to fack * i do
  inc(k, integer(fack mod j=0));
 fack:=fack*i;
end;

 Writeln(k);
 end.

[Aristarh Dark]

Хм... А я почему-то думал, что именно когда флаг установлен прерывания игнорируются. Хотя, имхо, винде все эти "фигли-мигли" пофиг.

[Bargest]

Сообщение от M.A.D.M.A.N.

Именно в такой последовательности "Clear Interrupt-Enable Flag" и "Set Interrupt-Enable Flag".

Под виндой не желательно делать ни то, ни другое. По-хорошему винда не даст юзать cli. Слишком опасно. Вроде выдается что-то типа Privileged instruction.
А вот под досом - вполне.

[M.A.D.M.A.N.]

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

Вроде выдается что-то типа Privileged instruction.

Причем эта проверка выполняется самим процессором. Т.е. по сути если дескриптору (descriptor privilege level) назначить нужный уровень (0), то работать будет

[Dmitry_DM]

Сообщение от M.A.D.M.A.N.

Именно в такой последовательности "Clear Interrupt-Enable Flag" и "Set Interrupt-Enable Flag".

В принципе второй цикл можно затолкать в первый.

Типа:

Код:

var fack:Int64;
 i, j,n,k:Integer;
 begin
 fack:=1;
 Readln(n);
for i:=2 to n do
begin
 for j := fack to fack * i do
  inc(k, integer(fack mod j=0));
 fack:=fack*i;
end;

 Writeln(k);
 end.

Есть тесты: ввод 4 вывод 8
А по вашему коду ввод 4 вывод 76808195

[M.A.D.M.A.N.]

Туплю чето.
I II III IV V VI VII VIII IX X

[PhoeniX]

Сокращаем количество проходов в 2 раза:

Код:

var
  i,fack: Int64;
  n,k: Integer;
begin
  fack:=1;
  Readln(n);
  for k:=2 to n do
    fack:=fack*k;
  k:=2;
  i:=2;
  while i <= fack div 2 do begin
    if (fack mod i) = 0 then
      inc(k);
    inc(i);
  end;
  Writeln(k);
end.

На больших значениях fack переменная типа integer никогда не доберётся до максимального значения (пример - fack = 14! = 87 178 291 200, Integer = -2 147 483 648..2 147 483 647). I тоже должна быть Int64. Но int64 не работает в циклах for-do, так что извращаемся.

[dr. F.I.N.]

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

"По заданному натуральному числу N необходимо вычислить количество натуральных чисел, которые являются делителями N! (факториала числа N)."

Ребят, вы меня извините, но:
1. Факториа́л числа n (обозначается n!, произносится эн факториа́л) — произведение всех натуральных чисел от 1 до n включительно.
2. Если для некоторого целого числа a и целого числа b существует такое целое число q, что bq=a то говорят, что число a делится нацело на b или что b делит a. При этом число b называется делителем числа a, делимое a будет кратным числа b, а число q называется частным от деления a на b.

Исходя из этого всего возникает вопрос: А зачем вообще считать факториал?
Эта задача - комбинаторная, а не расчетная.

[M.A.D.M.A.N.]

Дык задача из разряда прикладных, когда надо сделать нах никому ненужный алгоритм (например коля с васей решили померяться пиписьками, вася снял штаны, а коля побежал в москву, потом в асхтрахань, потом на камчатку, просчитать, сколько пыли было на правом ботинке васи, если известно, что длина пиписьки коли на 1/4 от трети длины четверти квадрата диаметра окружности вписанного в треугольник, угол которого равен углу между яйцами и коленом дяди пети больше на десять в минус четвертой, чем расстояние между луной и плутоном в день летнего солнцестояния в период засухи в африке).

И еще чтоб быстро работало.

[Bargest]

Причем эта проверка выполняется самим процессором. Т.е. по сути если дескриптору (descriptor privilege level) назначить нужный уровень (0), то работать будет

Ага, назначь. Вот так запросто. Учитывая, что GDT находится в памяти, которая недоступна для записи простым смертным.

Дык задача из разряда прикладных, когда надо сделать нах никому ненужный алгоритм (например коля с васей решили померяться пиписьками, вася снял штаны, а коля побежал в москву, потом в асхтрахань, потом на камчатку, просчитать, сколько пыли было на правом ботинке васи, если известно, что длина пиписьки коли на 1/4 от трети длины четверти квадрата диаметра окружности вписанного в треугольник, угол которого равен углу между яйцами и коленом дяди пети больше на десять в минус четвертой, чем расстояние между луной и плутоном в день летнего солнцестояния в период засухи в африке).

И еще чтоб быстро работало.

+1.

[M.A.D.M.A.N.]

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

Вот так запросто.

Пощелкал и готово