CTNOWN - Bội số chung nhỏ nhất

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      fo='';
      maxn=350;
      maxp=70;
var n:longint;
    p:array[0..maxp] of longint;
    f:array[0..maxn,0..maxp] of qword;
    re:array[1..maxn] of qword;

procedure rf;
begin
     assign(input,fi); reset(input);
     assign(OUTput,fo); rewrite(output);
end;

procedure prime;
var i,j,t:longint;
begin
     for i:=2 to maxn do
     begin
          t:=0;
          for j:=2 to trunc(sqrt(i)) do
              if i mod j=0 then inc(t);
          if t=0 then
          begin
               inc(p[0]); p[p[0]]:=i;
          end;
     end;
end;

function max(x,y:qword):qword;
begin
     if x>y then max:=x else max:=y;
end;

procedure pr;
var i,j:longint; t:qword;
begin
     prime;
     for i:=0 to maxn do f[i,0]:=1;
     for i:=0 to maxp do f[0,i]:=1;
     for i:=1 to maxn do
         for j:=1 to maxp do
         begin
              if (p[j]>i) or (p[j]=0) then break;
              f[i,j]:=max(f[i-1,j],f[i,j-1]);
              t:=p[j];
              while t<=i do
              begin
                   f[i,j]:=max(f[i,j],f[i-t,j-1]*t);
                   t:=t*p[j];
              end;
              if f[i,j]>re[i] then re[i]:=f[i,j];
         end;
end;

procedure wf;
var i,t:longint;
begin
  readln(t);
  for i:=1 to t do
  begin
   readln(n); writeln(re[n]);
  end;
     close(input);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Download