ac1010.pas

来自「某牛人写的acm.tongji.edu.cn上大部分ac的代码,仅供学习研究,请」· PAS 代码 · 共 56 行

program tju1010;
const
  max=999999;
  bitmask:array[0..7]of byte=(127,191,223,239,247,251,253,254);
  rightmask:array[0..8]of byte=(255,127,63,31,15,7,3,1,0);
var
  bits:array[0..255]of byte;
  prime:array[0..max shr 3]of word;
  count:array[0..max shr 3]of longint;
  m,n,q1,q2,r1,r2:longint;
procedure calbits;
  var
    i,j,x:byte;
  begin
    for i:=0 to 255 do begin
      x:=i;
      for j:=1 to 8 do begin
        if odd(x) then inc(bits[i]);
        x:=x shr 1;
      end;
    end;
  end;
procedure delprime(x:longint);
  var
    q,r:longint;
  begin
    q:=x shr 3;r:=x and 7;
    if prime[q] and bitmask[r]<prime[q] then dec(count[q]);
    prime[q]:=prime[q] and bitmask[r];
  end;
procedure calprime;
  var
    i,j:longint;
  begin
    fillchar(prime,sizeof(prime),255);
    for i:=0 to max shr 3 do count[i]:=8;
    delprime(0);delprime(1);
    for i:=2 to trunc(sqrt(max)) do begin
      j:=i shl 1;
      while j<=max do begin
        delprime(j);
        inc(j,i);
      end;
    end;
    for i:=1 to max shr 3 do inc(count[i],count[i-1]);
  end;
begin
  calbits;
  calprime;
  repeat
    read(m,n);
    q1:=m shr 3;r1:=m and 7;q2:=n shr 3;r2:=n and 7;
    writeln(count[q2]-count[q1]+bits[prime[q1] and rightmask[r1]]-bits[prime[q2] and rightmask[r2+1]]);
  until seekeof;
end.