NKABD - Số phong phú

Tác giả: RR

Ngôn ngữ: Pascal

const
  MAXN          =       100000;

var
  lt,m,p        :       array[1..MAXN] of longint;
  sum           :       array[1..MAXN] of int64;

procedure init;
    var
      i,gh,j,u:longint;
    begin
      gh:=trunc(sqrt(MAXN));
      for i:=1 to MAXN do
        begin
          p[i]:=i;
          lt[i]:=1;
          m[i]:=1;
        end;

      for i:=2 to gh do
      if p[i]=i then
        begin
          j:=i*i; u:=i;
          while (j<=MAXN) do
            begin
              p[j]:=i;
              m[j]:=u;
              while m[j] mod i=0 do
                m[j]:=m[j] div i;
              if m[j]=1 then lt[j]:=lt[u]+1
              else lt[j]:=0;
              inc(j,i); inc(u);
            end;
        end;

      sum[1]:=0;
      for i:=2 to MAXN do
        if lt[i]=0 then sum[i]:=sum[m[i]]*sum[i div m[i]]
        else sum[i]:=(int64(i)*p[i]-1) div (p[i]-1);
    end;

var
  i,l,r,cnt:longint;

begin
  init;
  read(l,r);
  for i:=l to r do
    if sum[i]-i>i then inc(cnt);
  writeln(cnt);
end.

Download