Cod sursa(job #290614)

Utilizator lsorin_94Lodoaba Sorin lsorin_94 Data 28 martie 2009 13:28:56
Problema Fractii Scor 50
Compilator fpc Status done
Runda concurs_cu_o_problema_usoara_si_una_medie Marime 0.74 kb
program fractii;
type vec=array[1..100000] of longint;
var v,a,b,c:vec;
    n,l:longint;
    r:int64;
    i,j:longint;
    f,t:text;
begin
  assign(f,'fractii.in'); reset(f);
  assign(t,'fractii.out'); rewrite(t);
  readln(f,n);r:=0;i:=0;j:=0; l:=trunc(sqrt(n));
  for i:=2 to l do
    if v[i]=0 then
      for j:=1 to n div i do
        v[i*j]:=i;
  for i:=l+1 to n do
    if v[i]=0
      then v[i]:=i;
  for i:=2 to n do
    begin
      a[i]:=v[i];
      j:=i div a[i];
      while j mod a[i]=0 do
        a[i]:=a[i]*v[i];
      b[i]:=i div a[i];
      if b[i]=1
        then c[i]:=i-i div v[i]
        else c[i]:=c[a[i]]*c[b[i]];
    end;
  for i:=2 to n do
    r:=r+c[i];
  r:=2*r+1;
  write(t,r);
  close(f); close(t);
end.