PersonalCorpus 版 (精华区)

148714 20:24:19
28 Feb 2002 Bozhang,HIT,P.R.China 1073 Pascal Accepted 0.1 sec 168K


var
    s:array[1..120000] of byte;
    n,m,i,j,k:integer;
begin
    readln(n);
    fillchar(s,sizeof(s),0);
    for i:=1 to 244 do begin s[i*i]:=1; if n=i*i then begin writeln(1);halt
end end;
    for k:=2 to 4 do
        for i:=1 to 60000 do if s[i]=k-1 then
            for j:=1 to 244 do begin
                m:=j*j+i;
                if m=n then begin
                    writeln(k); halt
                end;
                if s[m]=0 then s[m]:=k;
            end;
end.