ac1170.pas

某牛人写的acm.tongji.edu.cn上大部分ac的代码,仅供学习研究,请不要用来作弊

program tju1170;
const
  maxn=1000000;
  sqrtmaxn=trunc(sqrt(maxn));
  modulo=sqrtmaxn+1;
var
  unary:array[1..maxn]of byte;
  pre:array[2..sqrtmaxn]of word;
  last:array[0..sqrtmaxn]of word;
  n,i,m,f,t,debut,sqrdebut:longint;
begin
  unary[1]:=1;debut:=2;sqrdebut:=4;
  for n:=2 to maxn do begin
    unary[n]:=unary[n-1]+1;
    m:=n mod modulo;
    if n=sqrdebut then begin
      pre[debut]:=last[m];last[m]:=debut;
      inc(debut);sqrdebut:=sqr(debut);
    end;
    while last[m]>0 do begin
      f:=last[m];
      t:=unary[f]+unary[n div f];
      if t<unary[n] then unary[n]:=t;
      t:=(m+f) mod modulo;
      last[m]:=pre[f];pre[f]:=last[t];last[t]:=f;
    end;
  end;

  repeat
    read(n);
    writeln(unary[n]);
  until seekeof;
end.