比赛 noip-081029 评测结果 AAWTTAATTT
题目名称 最多因子数 最终得分 40
用户昵称 lc 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2008-10-29 21:53:07
显示代码纯文本
program ex1029_3;
 var
    f:array[0..40000] of longint;
    sum:array[1..100000] of longint;
    g:array[1..40000] of boolean;
    L,U,i,tm,max,ans:longint;

procedure ready;
 var
    i,j:longint;
 begin
  i:=2; j:=0;
  fillchar(g,sizeof(g),1);
  g[1]:=false;
  repeat
   inc(f[0]); f[f[0]]:=i; j:=i;
   while  j<=40000 do begin
      g[j]:=false;
      inc(j,i);
      end;
   while i<40000 do
     begin
     inc(i); if g[i] then break;
     end;
  until i=40000;
 end;

function fenjie(i:longint):longint;
 var
    k,tm,m:longint;

begin
  tm:=1;
  for k:=1 to f[0] do
   begin
   m:=0;
   if i=1 then break;
   while i mod f[k]=0 do
     begin
     inc(m);
     i:=i div f[k];
     end;
   tm:=tm*(m+1);
   if i<=100000 then if sum[i]<>-1 then begin tm:=tm*sum[i]; break end;
   end;
 fenjie:=tm;
end;


begin
 assign(input,'divisors.in');
 assign(output,'divisors.out');
 reset(input); rewrite(output);
 ready;
 readln(L,U);
 fillchar(sum,sizeof(sum),$FF);
 for i:=L to U do
  begin
  tm:=fenjie(i);
  if i<=100000 then sum[i]:=tm;
  if tm>max then begin max:=tm; ans:=i end;
  end;
 writeln('Between ',L,' and ',U,',',ans,' has a maximum of ',max,' divisors.');
 close(input); close(output);
end.