Помогите в решении задачи

[Аватар]

Да, выбрал те, произведение которых равно n. А нужно еще те, произведение которых делится нацело на на n. Для 12 считает 1*12, 2*6 и 3*4. А еще есть 8*9*10 дважды делится на 12

[evg_m]

только математика

1. любое число(<N) можно представить как ПРОИЗВЕДЕНИЕ ВСЕХ простых множителей q1...qm каждый из которых <=N (возможно с нулевой степенью)
n = q1^a1 * q2^a2 * ... * qm^am

2. факториал этого же числа суть произведение ТЕХ же множителей с ДРУГИМИ коэффициентами.
n! = q1^x1 * q2^x2 * ... * qm^xm
(x1, ... xm) вот это придется посчитать

3. степень числа ТЕ же множители и еще раз ДРУГИЕ коэффициенты
n^k = q1^(a1*k) * q2^(a2*k) * ... qm^(am*k)

4. КОГДА ОДНО число делится на другое нацело?
когда в их разложении на простые множители (см. п.1) степень при КАЖДОМ множителе для первого числа >= соответствующей степени второго числа

(qi^xi) делится нацело на (qi^yi) <==> xi >=yi

5. найти максимальное k такое что
a) n! делится нацело n^k <=> xi>=(ai*k) для всех i
б) n! НЕ делится нацело на n^(k+1) <=> НАЙДЕТСЯ такое i, где будет нарушено условие xi >=(ai*(k+1)), т.е. xi<(ai*(k+1))

[Аватар]

Лихо. А можно так. Заводим массив A[1..n] в котором 1,2,..,n.
n разложим на простые множители и в массив B[1..m] Для 12 В = [2,2,3]. И сколько раз удастся сократить полностью элементы B по элементам массива А то и результат. При каждом сокращении в A остается остаток от деления вплоть до 1

[Virel7779]

Я так и делал, у меня не получилось реализовать.(

[Virel7779]

Спасибо за наводку, пробую что-то делать

[Аватар]

Так вроде оно, только делфи и можно наверняка оптимальней

  SetLength(A,n);
  for i:=1 to n do A[i-1]:=i;

  i:=2; k:=n;
  while i<=k do begin
    if k mod i = 0 then begin
      SetLength(B,Length(B)+1);
      B[Length(B)-1]:=i;
      k:=k div i;
    end
    else Inc(i);
  end;

  k:=0;
  while True do begin
    for i:=0 to High(B) do begin
      Exists:=False;
      for j:=0 to High(A) do
        if A[j] mod B[i] = 0 then begin
          A[j]:=A[j] div B[i];
          Exists:=True;
          Break;
        end;
      if not Exists then Break;
    end;
    if not Exists then Break;
    Inc(k);
  end;

[Virel7779]

Спасибо за помощь. Проверю через время!

[Аватар]

Только оно не оптимально, для больших n по времени вылетит

Ближе к тому, что evg_m предлагал, без большого массива и считает оптимально для близких к 10^9. Динамический массив можно просто заменить на односвязный список. Для 1<n<=10^9. Для простых чисел близких к 10^9 (например 982451653) небольшой тормоз при разложении на множители

procedure TForm1.Button2Click(Sender: TObject);
type TMyRecord = record
       Number: Longint;
       Count: Longint;
     end;
var i,k,n,kMax: Longint;
    j: Int64;
    B: array of TMyRecord;
begin
  n:=StrToInt(Edit1.Text);

  i:=2; k:=n;
  while i<=k do begin
    if k mod i = 0 then begin
      SetLength(B,Length(B)+1);
      B[Length(B)-1].Number:=i;
      B[Length(B)-1].Count:=1;
      k:=k div i;
      while k mod i = 0 do begin
        Inc(B[Length(B)-1].Count);
        k:=k div i;
      end;
    end;
    Inc(i);
  end;

  kMax:=n;
  for i:=0 to Length(B)-1 do begin
    k:=0;
    j:=B[i].Number;
    while j<=n do begin
      Inc(k,n div j);
      j:=j*B[i].Number;
    end;
    k:=k div B[i].Count;
    if k<kMax then kMax:=k;
  end;

  Edit3.Text:=IntToStr(kMax);
end;

[Plague]

Inc(i);

Заменить на это. Зачем нам четные числа проверять?!

if i mod 2=0 then Inc(i) else Inc(i,2);

[Аватар]

Отож, вместо 18 сек за 9 отрабатывает для n=982451653